# Binary Trees

## #

OverviewA binary tree is a data structure where each node has at most **2 children nodes**. The 2 nodes are the left and right child respectively.

The top of the tree is a single node, the root.

Each node has a parent node except the root.

### #

Depth of a NodeThe depth of a node refers to the length of the path from a node to the root. The root itself has a depth of 0.

### #

Height of a TreeThe height of a tree is the length of path from the root node to the leaf nodes. A leaf node has a height of 0.

### #

Height of a NodeThe height of a node is the number of edges on the longest path from the node to a leaf. A leaf node will have a height of 0.

Note: The height of a node does not depend on the level it is on the tree. All leaf nodes have a height of 0.

*Note: A null node's height is sometimes given as -1.*

## #

Types of Binary Trees### #

Complete Binary TreeA complete binary tree has every level filled except maybe the last and all nodes in the last level are as far to the left as possible.

### #

Full Binary TreeA full binary tree (or proper/plane binary tree) is a tree where each node has 0 or 2 children.

### #

Perfect Binary Trees- Both full and complete. All lead nodes will be at same level and this level has maximum number of nodes.
- Has exactly 2
^{k}- 1 nodes (k = no. of levels)

## #

Implementation### #

NodeEach node has a value for itself and 2 references - 1 to the left child, 1 to the right child.

### #

Binary Tree### #

Height of a NodeIn above code to calculate the height of a node, we return `-1`

is a node is `None`

. When added to `1`

below, this will make the previous level 0.

### #

Size of a TreeThe size of a tree is the total number of nodes in the tree.

## #

Traversal AlgorithmsTraversing a tree refers to visiting each node exactly once. Trees can be traversed in depth-first order (DFO) or breadth-first order (BFO).

For DFO, there are 3 main methods:

- In-order
- Pre-order
- Post-order

### #

Pre-order TraversalAlgorithm:

- Capture/display current node's value
- Traverse left side with recursion
- Traverse right side with recursion

### #

In-order TraversalAlgorithm:

- Traverse left side with recursion
- Capture/display current node's value
- Traverse right side with recursion

### #

Post-order Traversal- Traverse left side with recursion
- Traverse right side with recursion
- Capture/display current node's value

## #

Level-order Traversal### #

OverviewLevel order traversal is when we traverse the binary tree at each level.

Example:

Level-order traversal of the above tree will output: `1,2,3,4,5`

.

### #

ImplementationAlgorithm:

- Enqueue root node
- Dequeue root node
- Enqueue root node's children, left then right
- Repeat till queue is empty

- Time complexity:
`O(n)`

where`n`

is the number of nodes in binary tree as we traverse entire tree - Space complexity:
`O(n)`

due to use of queue

### #

Tweak: Reverse Level OrderWith reverse level order, we obtain `4,5,2,3,1`

. For this we can use a stack instead of a queue.

The order of elements in the stack (from top to bottom) will be `4,5,2,3,1`

which means we need to push the right child of each node before the left child.

Finally, we pop out the stack till its empty to obtain the reverse level order.