Traversing a Binary Tree

Trees

In this post, we will see how to:

  1. Create a Binary Tree
  2. Traverse a Binary Tree using DFS
  3. Pre-order traversal of binary tree using iteration.
  4. Pre-order traversal of binary tree using recursion.
  5. In-order traversal of binary tree
  6. Post-order traversal of binary tree

Terminology

  • root: The root node
  • levels: There are 3 levels in the below tree
  • parent: Has atleast one child node
  • child: Has no child nodes
  • height: Number of levels in a tree
  • depth: Number of edges from root to leaf

trees

Traversal

Unlike traversing a list of values in an array or a linked list, traversing a tree requires deciding whether we are going to go left or right when we start at the root node. In other words, trees are not linear, so there is no clear way of traversing a tree. Several questions arise:

  • Suppose we start at root, do we go left first or right first?
  • Should we completely traverse one subtree or one section of the tree including all its descendants?
  • Should we traverse all the elements at the same level first?

Traversal in a tree is a bit more complicated but it is equally important. We can’t search or sort elements unless we have a way to make sure we can visit all elements first.

Mainly, there are two general ways of traversing a tree:

  • The first is called Depth First Search. In DFS, the philosophy is if there are children nodes to explore, then exploring them is its first priority.
  • The second is called Bredth First Search. In BFS, the priority is visiting every node on the same level we are currently on before visiting child nodes.

Breadth First Search:

  • Breadth First Search is also called “Level-Order” traversal.
  • We start at root then visit its children on the second level.
  • We are visiting all nodes at the same level before moving on to child nodes.

Depth First Search: There are several different approaches to DFS. First, we will see how to do pre-order traversal. To me pre says, check of a node as soon as you see it, before you traverse any further in the tree. There are other methods of traversal in which you check off nodes after you have seen their children.

We start at the root and immediately check off that we have seen it. Next, we pick one of the children. Normally left by convention, and check it off too. We continue traversing down the left most nodes until we hit a leaf node. We then check off the leaf and then go back up the parent. Now we traverse to the right child and check it off too.

preorder

NOTE: Average time complexity for these tree operations is O(log n)

Create a Binary Tree

A tree is just a collection of Nodes.

A node has a value, a left pointer, a right pointer.

So you need 2 classes, one for Node and one for Tree.

# this code makes the tree that we'll traverse

class Node(object):

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

    def set_value(self,value):
        self.value = value

    def get_value(self):
        return self.value

    def set_left_child(self,left):
        self.left = left

    def set_right_child(self, right):
        self.right = right

    def get_left_child(self):
        return self.left

    def get_right_child(self):
        return self.right

    def has_left_child(self):
        return self.left != None

    def has_right_child(self):
        return self.right != None

    # define __repr_ to decide what a print statement displays for a Node object
    def __repr__(self):
        return f"Node({self.get_value()})"

    def __str__(self):
        return f"Node({self.get_value()})"


class Tree():
    def __init__(self, value=None):
        self.root = Node(value)

    def get_root(self):
        return self.root

tree image

# create tree.
# pass in the root of the tree
tree = Tree('apple')
root = tree.get_root()

if root.has_left_child() == False:
    root.set_left_child(Node('banana'))

if root.has_right_child() == False:
    root.set_right_child(Node('cherry'))

root.get_left_child().set_left_child(Node('dates'))

Depth-first, pre-order traversal

Now that we have constructed our tree, it is time now to do our first traversal of this tree. We will use DFS, pre-order traversal.

Algorithm for traversing the tree in pre-order:

In pre-order traversal, we first visit the parent node, then the left child and then the right child.

For traversing this tree, we need a data structure to keep track of the nodes that we visited.

  • Visit the parent first
  • Visit the left child
  • Visit the right child

Use a Stack to track what nodes we visited

The act of visiting means, to push that node to the top of the stack. Once, we visited it, then we check if that node has a left child, if it does, then we visit that too. Repeat this until there is no left child. We then check, if there is any right child. If there is no right child, then we pop from the stack.

You can think of DFS as the act of pushing and poping from the Stack.

  • We push an element to the top of the stack when we first visit it.
  • At each node, we are going to ask a few questions. Do you have a left-child? Do you have a right-child? If the answer to both these questions is no, then we pop the element from the stack.

One of the difficult parts of working with DFS is coming up with verbiage to explain the code step-by-step. Instead, it is better to break the code into chunks. We will first try to implement parts of this algorithm without using a loop. So that we see each step closely.

class Stack(object):
    def __init__(self):
        self.items = list()

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.size() == 0:
            return None
        return self.items.pop()

    def top(self):
        if self.size() == 0:
            return None
        return self.items[-1]

    def size(self):
        return len(self.items)  

    def is_empty(self):
        return len(self.items) == 0

    def __repr__(self):
        s = "---top---\n"
        s += " \n".join(str(i) for i in self.items[::-1])
        s += "\n---bottom---"

        return s
# create a list called visit_order to keep track of the nodes we visited.
# we can then print this out to get our complete pre-order traversal output.
visit_order = list()

# define our stack
stack = Stack()

Recall that we already built the tree. The tree has get_root() method, which will get us the root node.

root = tree.get_root()
# start at the root node, visit it (which means add it to visit list)
# then push it to the top of the stack.

# push it to top of the stack
stack.push(root)
# lets use a print statement to check the state
print(f"The visit order is: {visit_order}. \nThe contents of the stack are: \n {stack}")
The visit order is: [].
The contents of the stack are:
 ---top---
Node(apple)
---bottom---
# visit it now
visit_order.append(root.get_value())
# lets use a print statement to check the state
print(f"The visit order is: {visit_order}. \nThe contents of the stack are: \n {stack}")
The visit order is: ['apple'].
The contents of the stack are:
 ---top---
Node(apple)
---bottom---

So, now what are we going to do with the Node at the top of the stack?. We check if it has a left_child. If it has a left child then we advance to left child and add it to top of the stack and then visit it.

# check if the node at top of stack has left child
if root.has_left_child():
    root = root.get_left_child()
    stack.push(root)
    visit_order.append(root.get_value())
# lets use a print statement to check the state
print(f"The visit order is: {visit_order}. \nThe contents of the stack are: \n {stack}")
The visit order is: ['apple', 'banana'].
The contents of the stack are:
 ---top---
Node(banana)
Node(apple)
---bottom---

We will re-run the above code again to check if the Node at the top of the stack has a left_child or not.

# check if the node at top of stack has left child
if root.has_left_child():
    root = root.get_left_child()
    stack.push(root)
    visit_order.append(root.get_value())
# lets use a print statement to check the state
print(f"The visit order is: {visit_order}. \nThe contents of the stack are: \n {stack}")
The visit order is: ['apple', 'banana', 'dates'].
The contents of the stack are:
 ---top---
Node(dates)
Node(banana)
Node(apple)
---bottom---
# check if the node at top of stack has left child
if root.has_left_child():
    root = root.get_left_child()
    stack.push(root)
    visit_order.append(root.get_value())
# lets use a print statement to check the state
print(f"The visit order is: {visit_order}. \nThe contents of the stack are: \n {stack}")
The visit order is: ['apple', 'banana', 'dates'].
The contents of the stack are:
 ---top---
Node(dates)
Node(banana)
Node(apple)
---bottom---

As you can see, we are repeating ourselves here, this part will go into a loop. Notice that at this stage, we are checking if our current node root has a left child and we are failing at that condition. So, the next thing we need to check if it has a right-child. This we do in the elif block.

# check if the node at top of stack has left child
if root.has_left_child():
    root = root.get_left_child()
    stack.push(root)
    visit_order.append(root.get_value())
elif root.has_right_child():
    root = root.get_right_child()
    stack.push(root)
    visit_order.append(root.get_value())
else:
    print("passing")
    pass
passing
# lets use a print statement to check the state
print(f"The visit order is: {visit_order}. \nThe contents of the stack are: \n {stack}")
The visit order is: ['apple', 'banana', 'dates'].
The contents of the stack are:
 ---top---
Node(dates)
Node(banana)
Node(apple)
---bottom---

So, you can see here that we are hitting the else case. This case handles the leaf-node case. So, as per the algorithm, when we hit the leaf-node, then we need to pop out the current node, and go to the parent node. In this case, we need to pop out dates and set root to be banana.

Ok, so when we are looping, our root will now be at banana, and it will again hit the else case and root will be set to apple. At this point, we will enter the elif case, where we have the has_right_child() true. Now, we set root to be the right child and push it to the top of the stack and visit it. Because we set root to the right child, the next time around, we will hit the else case, and this time, we will pop out cherry and go back to the parent.

Thus, inside the else statement, we need to do 2 things:

  • One, pop out the element at the top of the stack, because it doesn’t have any children.
  • two, check if the stack is non-empty, and then, get the top most element of the stack, which will be the parent.

NOW YOU SEE WHAT THE PROBLEM IS. We go back to the parent root node, it has_left_child(), so we start going down again. This should not happen! We need a way to keep track of the STATE, i.e, did we already visit left_child() and right_child(), if so skip going down. Eventually, our stack will by empty at which point, we need to exit the while loop.

def pre_order_with_stack_buggy(tree):
    visit_order = list()
    stack = Stack()
    node = tree.get_root()
    visit_order.append(node.get_value())
    stack.push(node)
    count = 0
    loop_limit = 7
    while(node and count < loop_limit):
        print(f"""
loop count: {count}
current node: {node}
stack:
{stack}
        """)
        count +=1
        if node.has_left_child():
            node = node.get_left_child()
            visit_order.append(node.get_value())
            stack.push(node)

        elif node.has_right_child():
            node = node.get_right_child()
            visit_order.append(node.get_value())
            stack.push(node)

        else:
            stack.pop()
            if not stack.is_empty():
                node = stack.top()
            else:
                node = None


    return visit_order
pre_order_with_stack_buggy(tree)
loop count: 0
current node: Node(apple)
stack:
---top---
Node(apple)
---bottom---


loop count: 1
current node: Node(banana)
stack:
---top---
Node(banana)
Node(apple)
---bottom---


loop count: 2
current node: Node(dates)
stack:
---top---
Node(dates)
Node(banana)
Node(apple)
---bottom---


loop count: 3
current node: Node(banana)
stack:
---top---
Node(banana)
Node(apple)
---bottom---


loop count: 4
current node: Node(dates)
stack:
---top---
Node(dates)
Node(banana)
Node(apple)
---bottom---


loop count: 5
current node: Node(banana)
stack:
---top---
Node(banana)
Node(apple)
---bottom---


loop count: 6
current node: Node(dates)
stack:
---top---
Node(dates)
Node(banana)
Node(apple)
---bottom---






['apple', 'banana', 'dates', 'dates', 'dates']

PUSH State on to the stack

As we found above, we need a way to keep track of whether we visited the children or not, otherwise, we end up in an infite loop. Instead of pushing the NODE onto the top-of-the-stack, we are going to push the STATE.

class State(object):
    def __init__(self,node):
        self.node = node
        self.visited_left = False
        self.visited_right = False

    def get_node(self):
        return self.node

    def get_visited_left(self):
        return self.visited_left

    def get_visited_right(self):
        return self.visited_right

    def set_visited_left(self):
        self.visited_left = True

    def set_visited_right(self):
        self.visited_right = True

    def __repr__(self):
        s = f"""{self.node}
visited_left: {self.visited_left}
visited_right: {self.visited_right}
        """
        return s
#sk
def pre_order_traversal(tree):

    # get the root of the tree
    # this will be what we will be looping over
    node = tree.get_root()

    # declare visit_order list
    # this is what we will be returning
    visit_order = list()

    # declare a stack to back-track
    stack = Stack()

    # declare a state instance to keep track of state
    # this is what we will be pushing to the top of the stack
    state = State(node) # don't think i need to

    # since this is pre-order traversal, we will first visit
    # the parent node. So, push the root node to top of the stack
    # that is, push the state to the top-of-the-stack
    stack.push(state)

    # add to visit_list
    visit_order.append(node.get_value())

    while node:  
        if node.has_left_child() and not state.get_visited_left():
            state.set_visited_left()
            node = node.get_left_child()
            state = State(node)
            stack.push(state)
            visit_order.append(node.get_value())
        elif node.has_right_child() and not state.get_visited_right():
            state.set_visited_right()
            node = node.get_right_child()
            state = State(node)
            stack.push(state)
            visit_order.append(node.get_value())
        else:
            # pop out that leaf node
            stack.pop()

            # get the node at the top of the stack
            # check if the top of the stack is not none
            if stack.top():
                state = stack.top()
                node = state.get_node()
            else:
                node = None
    return visit_order
pre_order_traversal(tree)
['apple', 'banana', 'dates', 'cherry']

Pre-order traversal with Recursion

def pre_order(tree):

    visit_order = list()

    def traverse(node):
        if node:
            # visit the node
            visit_order.append(node.get_value())

            # traverse left subtree
            traverse(node.get_left_child())

            # traverse right subtree
            traverse(node.get_right_child())

    traverse(tree.get_root())

    return visit_order
pre_order(tree)
['apple', 'banana', 'dates', 'cherry']

NOTE: We can’t define this as an outer function, because we won’t be able to see visit_order variable. You’d have to define visit_order outside of the function. Rather than putting this as a global variable, we can instead put this into pre_order() function.

# don't do this, use this as an inner function.
def traverse(node):
    if node:
        print(node.value)
        # visit the node
        visit_order.append(node.get_value())

        # traverse left subtree
        traverse(node.get_left_child())

        # traverse right subtree
        traverse(node.get_right_child())
def pre_order(tree):
    visit_order = list()

    def traverse(node):
        if node:
            # visit the node
            visit_order.append(node.get_value())

            # traverse left subtree
            traverse(node.get_left_child())

            # traverse right subtree
            traverse(node.get_right_child())

    traverse(tree.get_root())

    return visit_order
pre_order(tree)
apple
banana
dates
cherry





['apple', 'banana', 'dates', 'cherry']

In-order traversal of the Tree

def in_order(tree):
    visit_order = list()

    def traverse(node):
        if node:
            # traverse left subtree
            traverse(node.get_left_child())

            # visit the node
            visit_order.append(node.get_value())

            # traverse right subtree
            traverse(node.get_right_child())

    traverse(tree.get_root())

    return visit_order
in_order(tree)
['dates', 'banana', 'apple', 'cherry']

Post-order traversal of the Tree

def post_order(tree):
    visit_order = list()

    def traverse(node):
        if node:
            # traverse left subtree
            traverse(node.get_left_child())

            # traverse right subtree
            traverse(node.get_right_child())

            # visit the node
            visit_order.append(node.get_value())

    traverse(tree.get_root())

    return visit_order
post_order(tree)
['dates', 'banana', 'cherry', 'apple']