# Binary Trees

## Overview#

A 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 Node#

The 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 Tree#

The 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 Node#

The 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 Tree#

A 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 Tree#

A 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 2k - 1 nodes (k = no. of levels)

## Implementation#

### Node#

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

class Node(object):
def __init__(self, value:
self.value = value
self.left = None
self.right = None

### Binary Tree#

class BinaryTree(object):
def __init__(self, root_value):
self.root = Node(root_value)

### Height of a Node#

def height(node):
if node is None:
return -1
left_height = height(node.left)
right_height = height(node.right)
return 1 + max(left_height, right_height)

In 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 Tree#

The size of a tree is the total number of nodes in the tree.

def count_size(node):
if node is None:
return 0
left_size = count_size(node.left)
right_size = count_size(node.right)
return 1 + left_size + right_size

## Traversal Algorithms#

Traversing 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:

1. In-order
2. Pre-order
3. Post-order

### Pre-order Traversal#

Algorithm:

1. Capture/display current node's value
2. Traverse left side with recursion
3. Traverse right side with recursion
def pre_order(node):
result = []
if node:
result.append(node.value)
result += pre_order(node.left)
result += pre_order(node.right)
return result

### In-order Traversal#

Algorithm:

1. Traverse left side with recursion
2. Capture/display current node's value
3. Traverse right side with recursion
def in_order(node):
result = []
if node:
result += in_order(node.left)
result.append(node.value)
result += in_order(node.right)
return result

### Post-order Traversal#

1. Traverse left side with recursion
2. Traverse right side with recursion
3. Capture/display current node's value
def post_order(node):
result = []
if node:
result += post_order(node.left)
result += post_order(node.right)
result.append(node.value)
return result

## Level-order Traversal#

### Overview#

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

Example:

1
/ \
2 3
/ \
4 5

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

### Implementation#

Algorithm:

1. Enqueue root node
2. Dequeue root node
3. Enqueue root node's children, left then right
4. Repeat till queue is empty
def levelOrder(root):
if(root is None):
return []
queue = []
all_results = []
queue.append(root)
while(len(queue) > 0):
to_enqueue = []
result = []
# clear the current level first
while(len(queue) > 0):
curr = queue.pop(0)
result.append(curr.val)
if(curr.left):
to_enqueue.append(curr.left)
if(curr.right):
to_enqueue.append(curr.right)
if(len(result) > 0):
all_results.append(result)
• 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
With 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.