An Introduction to Binary Trees in Python

How to create and traverse binary trees using Python

A tree is a special data structure that consists of nodes connected by edges. They are non-linear and can be understood as a special kind of graph without any cycle.

A binary tree is a special variant of a tree data structure. In a binary tree, a parent node can have at most two children nodes. Here is an illustration of a binary tree:

• Here node 1 is known as the root node as it has no parent.
• Root 1 has two children: subtree 2 and subtree 3.
• Nodes 4 and 5 are children of node 2. Nodes 6 and 7 are children of node 3.
• Nodes 4, 5, 6, and 7 are known as leaf nodes as they don’t have any children.

From the definition, we know a node of a binary tree can have at most two children. So, if a node has one that's fine:

This is a brief overview of a binary tree and should be enough to move on to the Python implementation. To learn more about binary tree properties read this:

In this article, I will discuss how to create binary trees in Python. I will also share different tree traversing techniques and implement some interesting properties of binary trees.

How To Create a Binary Tree in Python

A binary tree node has three things associated with it:

• The value of the node
• A pointer or reference to its left child
• A reference to its right child

If we consider node 1:

So, we can define a Node class with the three properties:

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

This represents a single node of a binary tree. Initially, the root node will not have any left or right child. That is why initially both left and right are set to None. As we continue building the tree left and right will have the pointer of a node’s left and right child.

Now let’s build the tree from the above example:

root = Node(1)
"""
    1
  /   \
  X   X

# here X represents None
"""

root.left = Node(2)
root.right = Node(3)
"""
      1
    /   \
   2     3
  / \   / \
  X X   X X
"""

root.left.left = Node(4)
root.left.right = Node(5)
"""
           1
       /       \
      2         3
    /   \     /   \
  4      5   X    X
 / \    / \
 X X    X X
"""

root.right.left = Node(6)
root.right.right = Node(7)
"""
             1
         /        \
        2          3
      /   \      /   \
    4      5    6     7
   / \    / \  / \   / \
   X X    X X  X X   X X
"""

This is how we can construct a binary tree using Python. Now let’s implement different tree traversing techniques using Python.

Tree traversal algorithms are:

• BFS (Breadth-First Search)
• DFS (Depth-First Search)

BFS

The breadth-first technique uses level-wise traversing. See the below example:

A Queue data structure can help us to implement BFS. Let’s illustrate how:

BFS = []
queue = [1] // We start with the root node.

queue.pop() // 1
queue.push(2) and queue.push(3)
BFS = [1, ]
queue = [2, 3]

queue.pop() // 2
queue.push(4) and queue.push(5)
BFS = [1, 2, ]
queue = [3, 4, 5]

queue.pop() // 3
queue.push(6) and queue.push(7)
BFS = [1, 2, 3, ]
queue = [4, 5, 6, 7]

queue.pop() // 4
// 4 is a leaf node. So no push
BFS = [1, 2, 3, 4, ]
queue = [5, 6, 7]

queue.pop() // 5
BFS = [1, 2, 3, 4, 5]
queue = [6, 7]

queue.pop() // 6
BFS = [1, 2, 3, 4, 5, 6, ]
queue = [7]

queue.pop() // 7
BFS = [1, 2, 3, 4, 5, 6, 7]
queue = []

Queue is empty. That means we are done traversing.

Python implementation of BFS:

def bfs(root):
    # in case the tree is empty
    if not root:
        return

    queue = [] # using a list as a queue
    queue.append(root) # initially put the root into queue

    # keep popping until the queue is empty
    while queue:
        currNode = queue.pop(0) # pop(0) to achieve FIFO order
        
        # simply print the current node,
        # alternatively use a list to store the nodes,
        # and return the traversal list from the function, when done traversing
        print(currNode.val, end=" ")
        
        # if current node has a left child,
        # put it's reference to queue
        if currNode.left:
            queue.append(currNode.left)

        # if current node has a right child,
        # put it's reference to queue
        if currNode.right:
            queue.append(currNode.right)

bfs(root)
# output: 1 2 3 4 5 6 7

DFS

The depth-first technique uses depth-wise traversing. See the example below:

We can use a Stack for DFS. Let’s understand that with an illustration:

DFS = []
stack = [1] // We start with the root node.

stack.pop() // 1
stack.push(3) and stack.push(2)
DFS = [1, ]
stack = [2, 3]

stack.pop() // 2
stack.push(5) and stack.push(4)
DFS = [1, 2, ]
queue = [4, 5, 3]

stack.pop() // 4
// 4 is leaf node, so no push
DFS = [1, 2, 4, ]
stack = [5, 3]

stack.pop() // 5
// 5 is a leaf node. So no push
DFS = [1, 2, 4, 5, ]
stack = [3]

stack.pop() // 3
stack.push(7) and stack.push(6)
DFS = [1, 2, 4, 5, 3, ]
stack = [6, 7]

stack.pop() // 6
// 6 is leaf node, so no push
DFS = [1, 2, 4, 5, 3, 6, ]
satck = [7]

stack.pop() // 7
// 7 is leaf node, so no push
DFS = [1, 2, 4, 5, 3, 6, 7]
stack = []

Stack is empty. That means we are done traversing.

We are doing it using the LIFO order of a stack. The node that entered the stack last will be visited first.

Now let’s see the Python implementation for DFS:

def dfsStack(root):
    if not root:
        return

    stack = []
    stack.append(root)
    
    while stack:
        currNode = stack.pop() # pop() gives us the LIFO order of stack

        print(currNode.val, end=" ")
        
        # right subtree first
        if currNode.right:
            stack.append(currNode.right)

        if currNode.left:
            stack.append(currNode.left)

dfs(root)
# output: 1 2 4 5 3 6 7

If you observe the code you will see I am putting the right child of the current node to the stack before the left child. This is for the LIFO property of the stack. If we want to get the left child first, we need to put the right child before the left child in the stack. This way the left child will always be on the top of the stack.

What will happen if we put the left child first? See the code and output below:

def dfsStack(root):
    if not root:
        return

    stack = []
    stack.append(root)

    while stack:
        currNode = stack.pop()

        print(currNode.val, end=" ")
        
        # left subtree first
        if currNode.left:
            stack.append(currNode.left)

        if currNode.right:
            stack.append(currNode.right)

dfs(root)
# output: 1 3 7 6 2 5 4

This way we will also get the DFS traversal, but we will traverse the right subtree first.

Recursive DFS

DFS can also be implemented using recursion. If we use recursion, we don’t need to maintain a stack ourselves. Instead, the recursion call stack will take care of this for us:

def dfs(root):
    if not root:
        return

    print(root.val, end=" ")
    dfs(root.left)
    dfs(root.right)

dfs(root)
# output: 1 2 4 5 3 6 7

This is actually a variant of recursive DFS and is called pre-order traversal. Recursive DFS has three variants:

• Pre-order traversal
• Post-order traversal
• In-order traversal

Pre-order, Post-order, and In-order

The way we visit the root (parent) determines whether it is pre-order or post-order or in-order. If we visit the root first, then the left subtree, then the right subtree it is called pre-order traversal. If we visit the left subtree, then the subtree, then the root it is called post-order traversal. And if we visit the left subtree, then the root, then the right subtree it is called in-order traversal. So,

root --> left --> right (pre-order)
left --> right --> root (post-order)
left --> root --> right (in-order)

Preorder traversal in Python:

def dfsPreorder(root):
    if not root:
        return

    print(root.val, end=" ")
    dfsPreorder(root.left)
    dfsPreorder(root.right)

Postorder traversal in Python:

def dfsPostorder(root):
    if not root:
        return

    dfsPostorder(root.left)
    dfsPostorder(root.right)
    print(root.val, end=" ")

Inorder traversal in Python:

def dfsInorder(root):
    if not root:
        return

    dfsInorder(root.left)
    print(root.val, end=" ")
    dfsInorder(root.right)

In-order Traversal of a Binary Search Tree (BST)

Inorder traversal of a binary search tree gives us an interesting property. A binary search tree is a special kind of binary tree with the following properties:

• The left subtree of a node contains only nodes with values lesser than the value of that node.
• The right subtree of a node contains only nodes with values greater than the value of that node.
• The left and right subtree both should also be a binary search tree.

Here is an example of a binary search tree:

What is so interesting about the in-order traversal of a BST? Let’s see:

The in-order traversal of the above tree is 1, 2, 3, 4, 5, 6, 7. It is giving us a sorted order.

Searching a node in a binary search tree is similar to searching for an element in a sorted list.

We know if the list is sorted we can search for an element in O(log n) time. Similarly searching for a node in a BST is done in O(log n) complexity, where n is the number of nodes.

So using the in-order traversing technique we can tell if a binary tree is a BST or not. If the in-order traversal of a binary tree gives us a sorted sequence we can be sure that the tree is in fact a BST.

An implementation to validate BST can be this:

def isValidBST(root):
    traversal = []

    def inorder(root):
        if not root:
            return

        inorder(root.left)
        traversal.append(root.val)
        inorder(root.right)

    inorder(root)
     
    # if the traversal list is not sorted,
    # the tree is not a binary search tree
    for i in range(1, len(traversal)):
        if traversal[i] <= traversal[i-1]:
            return False

    return True

This is actually a famous LeetCode problem. Here is the problem link:

Get All Paths From Root Node to Leaf Nodes

We may want to get the paths from the root to each of its leaf nodes:

We can do that by keeping track of paths as we traverse the tree level-wise:

def rootToLeafPaths(root):
    if not root:
        return []

    paths = [] # to store all the paths from root to leafs
    queue = []
    queue.append([root, [root.val]])

    while queue:
        currNode, currPath = queue.pop(0)
        
        # if a node doesn't have left and right child, it is a leaf node.
        # so push this path to the paths list
        if not currNode.left and not currNode.right:
            paths.append(currPath)

        if currNode.left:
            queue.append([currNode.left, currPath + [currNode.left.val]])
        if currNode.right:
            queue.append([currNode.right, currPath + [currNode.right.val]])

    return paths

print(rootToLeafPaths(root))
# output: [[1, 2, 3], [1, 2, 4], [1, 5, 6], [1, 5, 7]]

There are some interesting practice problems in LeetCode that can be solved using this concept:

All the codes discussed in this article are here in one place:

Conclusion

In this article, I explained some important concepts of binary trees and how to implement them in Python. I hope this will give you a solid base for solving other tree-based problems. Thanks for reading!

If you find this article helpful, you may want to take a look at my other related reads: