#### Binary Trees Boot CampBootcampTrees

A Binary Tree is a data structure in which each node has a value, a pointer to a left child node and a pointer to a right child node.

If you are given a tree problem make sure to clarify immediately the properties of the given tree: are you given a BST (Binary Search Tree), a simple BT or another type of tree? Do nodes have pointers to their parent?

Balanced binary tree: height of the tree is O(logn). AVL trees maintain the property that the difference between the height of the left subtree and the height of the right subtree is 1.

Full Binary tree: every node has 0 or 2 children.

Complete trees: all levels are completely filled except for possibly the last one and the last level is filled from left to right (Heap is an example of a complete tree).

Perfect tree: all internal nodes have 2 children and all leaves are at the last level

Heap (max): a complete binary tree where each node has a value higher than its children.

##### Tree traversal

Most tree questions will require some sort of tree traversal to be solved. A tree can be traversed in two ways: DFS (Depth First Search) and BFS (Breadth First Search).

``````void dfs(BTNode node) {
if (node == null) {
return;
}

dfs(node.left);
System.out.println(node.data);
dfs(node.right);
}
``````

DFS can be performed in three different ways:

1. in-order traversal: left-root-right
2. pre-order traversal: root-left-right
3. post-order traversal: left-right-root
``````void bfs(BTNode root) {

while(!queue.isEmpty()) {
BTNode node = queue.remove();
System.out.println(node.data);

if (node.left != null)