Binary Trees

Binary Trees

This article introduces the basic concepts of binary trees, and then works through a series of practice problems with solution code in Python. Binary trees have an elegant recursive pointer structure, so they are a good way to learn recursive pointer algorithms.

Introduction To Binary Trees

A binary tree is made of nodes, where each node contains a left pointer, a right pointer, and a data element. The root pointer points to the topmost node in the tree.

(source: Leaf it up to binary trees )

The left and right pointers recursively point to smaller subtrees on either side. A null pointer represents a binary tree with no elements--the empty tree.

The formal recursive definition is: a tree is called binary tree if each node has zero child, one child, or two childern.

Types of Binary Trees

  • Strict Binary Tree: each node has exactly two children or no children.

  • Full Binary Tree: each node has exactly two children and all leaf nodes are at the same level.

  • Complete Binary Tree: every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Structure of Binary Trees

Now let us define the structure of a binary tree. One way to represent a node (which contains data) is to have two links which points to left and right children along with data fields. In Python, the binary tree is built with a node type like this ...

In [1]:
# Binary Tree node class
class BinaryTreeNode:
    def __init__(self, data, left=None, right=None):
        """defines a BT node with data, left child, and right child pointers"""
        self.data = data
        self.left = left
        self.right = right

Now let us define the actual binary tree. We will create a new class and initialize it with the root node

In [2]:
# Binary Tree class 
class BinaryTree:
    def __init__(self, root=None):
        self.root = root

In the next paragraph, we will create the following binary tree

In [3]:
# create a binary tree and set 10 as root node
BT = BinaryTree(BinaryTreeNode(10))

# Add child nodes 9, 7 to root node 
BT.root.left = BinaryTreeNode(9)
BT.root.right = BinaryTreeNode(7)

# Add child nodes 8, 6 to node 9
BT.root.left.left = BinaryTreeNode(8)
BT.root.left.right = BinaryTreeNode(6)

# Add child nodes 2, 4 to node 7
BT.root.right.left = BinaryTreeNode(2)
BT.root.right.right = BinaryTreeNode(4)
In [4]:
BT.root.data, BT.root.left.data, BT.root.right.data
Out[4]:
(10, 9, 7)

Binary Tree Traversals

The process of visiting all nodes of a tree is called tree traversal. Each node is processed only once but it may be visited more than once.

There are three main traversal methods:

  • Preorder (current node (D) -> Left node (L) -> Right node (R)) Traversal
  • Inorder (Left node (L) -> current node (D) -> Right node (R)) Traversal
  • Postorder (Left node (L) -> Right node (R) -> current node (D)) Traversal

There is another traversal method which does not depend on the above orders and it is:

  • Level Order Traversal: This method is inspired from Breadth First Search

(source: https://en.wikipedia.org/wiki/Breadth-first_search)

PreOrder Traversal

  • Each node is processed before either of its subtrees.
  • Even though each node is processed before the subtrees, this method still requires that some information must be maintained while moving down the tree.
  • Therefore, processing must return to the right subtree after finishing the processing of the left subtree. To move to the right subtree after processing the left subtree, we must maintain the root information. The suitable data structure for such task is a stack.

Preorder traversal is defined as follows:

  • Visit the root.
  • Traverse the left subtree in Preorder
  • Traverse the right subtree in Preorder
In [5]:
def preorder_traversal_recursive(root):
    """Function performs preorder traversal recursively. The nodes are printed 
    in traversal order."""

    if root is None:
        return

    print(root.data, end=' ')
    preorder_traversal_recursive(root.left)
    preorder_traversal_recursive(root.right)
In [6]:
preorder_traversal_recursive(BT.root)
10 9 8 6 7 2 4 
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

For an iterative solution, in order to simulate a stack, we use Python's list data structure. The push() method will be simulated by append() and the pop() method will be simulate by pop().

In [7]:
def preorder_traversal_iterative(root):
    """Function performs preorder traversal iteratively."""

    if root is None:
        return

    stack = []
    stack.append(root)

    while stack:
        current = stack.pop()
        print(current.data, end=' ')
        if current.right is not None:
            stack.append(current.right)

        if current.left is not None:
            stack.append(current.left)
In [8]:
preorder_traversal_iterative(BT.root)
10 9 8 6 7 2 4 
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

InOrder Traversal

In InOrder traversal, the root is visited between the subtrees. InOrder traversal is defined as follows:

  • Traverse the left subtree in Inorder
  • Visit the root
  • Traverse the right subtree in InOrder
In [9]:
def inorder_traversal_recursive(root):
    """Function performs inorder traversal recursively. The nodes are printed 
    in traversal order."""

    if root is None:
        return

    inorder_traversal_recursive(root.left)
    print(root.data, end=' ')
    inorder_traversal_recursive(root.right)
In [10]:
inorder_traversal_recursive(BT.root)
8 9 6 10 2 7 4 
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

PostOrder Traversal

In PostOrder traversal, the root is visited after both subtrees. PostOrder traversal is defined as follows:

  • Traverse the left subtree in Postorder
  • Traverse the right subtree in PostOrder
  • Visit the root
In [11]:
def postorder_traversal_recursive(root):
    """Function performs postorder traversal recursively. The nodes are printed 
    in traversal order."""

    if root is None:
        return

    postorder_traversal_recursive(root.left)
    postorder_traversal_recursive(root.right)
    print(root.data, end=' ')
In [12]:
postorder_traversal_recursive(BT.root)
8 6 9 2 4 7 10 
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

Level Order Traversal

Level Order Traversal is defined as follows:

  • Visit the root
  • While traversing level $l$, keep all the elements at level $l+1$ in queue.
  • Go to the next level and visit all the nodes at that level.
  • Repeat this until all levels are completed
In [13]:
import queue


def level_order(root):
    if root is None:
        return

    q = queue.Queue()
    q.put(root)

    while not q.empty():
        current = q.get()
        print(current.data, end=' ')

        if current.left is not None:
            q.put(current.left)
        if current.right is not None:
            q.put(current.right)
In [14]:
level_order(BT.root)
10 9 7 8 6 2 4 
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

Binary Tree Problems

Here are 4 binary tree problems with their Python implementations. Reading about a data structure is a fine introduction, but at some point the only way to learn is to actually try to solve some problems starting with a blank sheet of paper. To get the most out of these problems, you should at least attempt to solve them before looking at the solution. Even if your solution is not quite right, you will be building up the right skills. With any pointer-based code, it's a good idea to make memory drawings of a a few simple cases to see how the algorithm should work.

The following problems will use the following tree as an example:

Problem-1: Give algorithms for finding maximum and minimum element in a binary tree

Solution-1:

  • Find the maximum/minimum element in left subtree
  • Find the maximum/minimum element in right subtree
  • Compare them with the root data and select the one which is giving the maximum/minimum value.
In [15]:
def find_maximum(root):
    """finds and returns maximum element in a binary tree"""
    maximum = float("-infinity")
    if root is None:
        return maximum

    res = root.data
    lres = find_maximum(root.left)
    rres = find_maximum(root.right)
    return max(max(lres, rres), res)
In [16]:
print(find_maximum(BT.root))
10
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$
In [17]:
def find_minimum(root):
    """finds and returns minimum element in a binary tree"""
    #global minimum
    minimum = float("infinity")
    if root is None:
        return minimum
        
    res = root.data    
    lres = find_minimum(root.left)
    rres = find_minimum(root.right)
    
    return min(min(lres, rres), res)
In [18]:
find_minimum(BT.root)
Out[18]:
2
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

Solution-2:

  • Using level order traversal: observe the current node's data while removing the element from the queue.
In [19]:
import queue
def find_max_level_order(root):
    if root is None:
        return 
    
    q = queue.Queue()
    q.put(root)
    maximum = float("-infinity")
    while not q.empty():
        current = q.get()
        maximum = max(maximum, current.data)
        
        if current.left is not None:
            q.put(current.left) 
        if current.right is not None:
            q.put(current.right)
            
    return maximum
In [20]:
find_max_level_order(BT.root)
Out[20]:
10
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

Problem-2: Searching an element in a binary Tree

Solution-1:

  • Return 1 if a node with data is found in the tree.
  • Recurse down the tree, choose left or right by comparing data with each node's data
  • Return -1 if not found
In [21]:
def find_element(root, data):
    if root is None:
        return -1
    
    if root.data == data:
        return 1
    
    else:
        
        temp = find_element(root.left, data)
        if temp == 1: # if the element is found
            return temp 
        else:  # Search in the right subtree 
            return find_element(root.right, data)
In [22]:
find_element(BT.root, 14)
Out[22]:
-1
In [23]:
find_element(BT.root, 2)
Out[23]:
1

Solution-2:

  • Use level order traversal for solving this problem.
  • The only change required in level order traversal is, checking whether the current node data is equal to the element we are looking for.
In [24]:
def find_element_level_order(root, data):
    """Function that search for an element in a given binary tree.
    Returns 1 if the element is found, and -1 if not found."""
    if root is None:
        return

    q = queue.Queue()
    q.put(root)

    while not q.empty():
        current = q.get()

        if current.data == data:
            return 1
        else:
            if current.left is not None:
                q.put(current.left)

            if current.right is not None:
                q.put(current.right)

    return -1  # if not found
In [25]:
find_element_level_order(BT.root, 14)
Out[25]:
-1
In [26]:
find_element_level_order(BT.root, 2)
Out[26]:
1
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

Problem-3: finding the size of a binary tree

Solution-1:

  • Calculate the size of left and right subtrees recursively
  • Add 1 (current node) and return to its parent
In [27]:
def find_size(root):
    """Function to find the size of a binary tree """
    if root is None:
        return 0 
    
    return find_size(root.left) + find_size(root.right) + 1
In [28]:
find_size(BT.root)
Out[28]:
7

Solution-2:

  • Use level order traversal
In [29]:
def find_size_using_level_order(root):
    if root is None:
        return 0
    
    q = queue.Queue()
    q.put(root)
    counter = 0
    while not q.empty():
        current = q.get()
        counter += 1
        if current.left is not None:
            q.put(current.left)
            
        if current.right is not None:
            q.put(current.right)
            
    return counter
In [30]:
find_size_using_level_order(BT.root)
Out[30]:
7
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

Problem-4: Print the level order data in reverse order

Solution:

  • Use a stack to simulate Last In First Out (LIFO) in addition to the queue for level order traversal
In [31]:
def reverse_level_order_traversal(root):
    """Function for printing the level order data in reverse order"""
    if root is None:
        return

    q = queue.Queue()
    stack = []
    q.put(root)

    while not q.empty():
        current = q.get()
        stack.append(current)
        if current.left is not None:
            q.put(current.left)

        if current.right is not None:
            q.put(current.right)

    while stack:
        print(stack.pop().data, end=' ')
In [32]:
level_order(BT.root)
10 9 7 8 6 2 4 
In [33]:
reverse_level_order_traversal(BT.root)
4 2 6 8 7 9 10 

Comments