There are two ways to describe the shape of a tree. Trees can be *wide*, meaning that each node has many children. And trees can be *deep*, meaning that there are many parent-child connections with few siblings per node. Trees can be both *wide* and *deep* at the same time.

In a *binary search tree*, parent nodes can have a maximum of two children. These children are called the “left child” and the “right child”. A binary search tree requires that the values stored by the left child are **less** than the value of the parent, and the values stored by the right child are **greater** than that of the parent.

Trees in computer science are often talked about similarly to family trees. A tree node that references one or more other nodes is called a “parent”.

A tree node can be a “parent” and a “child” simultaneously, because they are not exclusive. For instance, a node ‘b’ can be the child of node ‘a’, while being the parent to nodes ‘d’ and ‘e’. However, a child can only have one parent, while a parent can have multiple children.

Trees are a data structure composed of nodes used for storing hierarchical data.

Each tree node typically stores a value and references to its child nodes.

A tree node contains a value, and can also include references to one or more additional tree nodes which are known as “children”.

To implement a general Tree data structure, we can create a `TreeNode`

class in Java with the following behavior:

- constructor with
`data`

and`children`

instance variables `.addChild()`

method to add a child to the TreeNode`.removeChild()`

method to remove a child from the descendants of the TreeNode

and a `Tree`

class with the following behavior:

`.print()`

method to print the tree`.depthFirstTraversal()`

method that prints the depth-first traversal of the tree`.breadthFirstTraversal()`

method that prints the breadth-first traversal of the tree

A `TreeNode`

has two `.addChild()`

methods.

public void addChild(TreeNode child) {this.children.add(child);}

public void addChild(Object childData) {TreeNode child = new TreeNode(childData);this.children.add(child);}

A `TreeNode`

should have `.removeChild()`

methods that take either a specific `TreeNode`

instance or a piece of data to search for. The implementation looks like this:

public void removeChild(TreeNode childToRemove) {if (this.children.isEmpty()) {return;} else if (this.children.contains(childToRemove)) {this.children.remove(childToRemove);return;} else {for (TreeNode child : this.children) {child.removeChild(childToRemove);}}}

public void removeChild(Object data) {if (this.children.isEmpty()) {return;}for (TreeNode child : this.children) {if (child.data == data) {removeChild(child);return;}}for (TreeNode child : this.children) {child.removeChild(data);}}

The `.depthFirstTraversal()`

method in the `Tree`

class should print the depth-first traversal of the tree using recursion. It takes nothing and returns nothing.

The code looks like this:

public void depthFirstTraversal(TreeNode current) {System.out.print(current.data + " ");for (TreeNode child : current.children) {depthFirstTraversal(child);}}

The `.breadthFirstTraversal()`

method in the `Tree`

class should print the breadth first traversal of the tree. It takes nothing and returns nothing. To implement this, we use a `Queue`

data structure to maintain the order of children added.

The code looks like this:

public void breadthFirstTraversal() {TreeNode current = this.root;Queue<TreeNode> queue = new LinkedList<>();queue.add(current);while (!queue.isEmpty()) {current = queue.poll();System.out.print(current.data + " ");queue.addAll(current.children);}}