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