### Wide and deep trees

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.

### Binary search tree

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.

### Nodes as parents

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 composed of nodes

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.

### Tree nodes children

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

### Trees In Java Overview

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

### Trees In Java - Add Child

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);
}
```

### Trees In Java - Remove 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);
}
}
```

### Trees In Java - Depth First Traversal

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);
}
}
```

### Trees In Java - Breadth First Traversal

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);
}
}
```