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)
# add the next level
queue += to_enqueue
return all_results
  • 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 Order#

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.

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