Binary Tree Traversal

In computer science, trees are widely used to represent hierarchical relationships between elements. Tree traversal algorithms allow us to systematically explore and manipulate the elements in a tree.

There are several common methods for tree traversal, including:

Pre-order traversal: In this method, we first visit the current node, then recursively traverse the left subtree, and finally traverse the right subtree. This results in visiting the nodes in a “root-left-right” order.

In-order traversal: Here, we first traverse the left subtree, then visit the current node, and finally traverse the right subtree. In-order traversal results in visiting the nodes in a “left-root-right” order. In binary search trees, an in-order traversal would give us the nodes in ascending order.

Post-order traversal: This method involves traversing the left subtree, then the right subtree, and finally visiting the current node. Post-order traversal gives us the nodes in a “left-right-root” order. This traversal is commonly used to delete nodes from a tree.

Level-order traversal: Also known as breadth-first traversal, this method visits the nodes level by level, starting from the root and moving down each level before proceeding to the next. It uses a queue data structure to keep track of the nodes to be visited.

Each traversal method has its own use cases and advantages depending on the problem. They allow us to perform various operations on tree nodes, such as searching, inserting, deleting, or printing the values.

Tree traversal: Depth-first traversal (dotted path) of a binary tree

• Pre-order (node visited at position red ●):
  F, B, A, D, C, E, G, I, H;
• In-order (node visited at position green ●):
  A, B, C, D, E, F, G, H, I;
• Post-order (node visited at position blue ●):
  A, C, E, D, B, H, I, G, F.

Implementation:

Define the binary tree.

class TreeNode:
  def __init__(self, data):
    self.data = data
    self.leftchild = None
    self.rightchild = None

NewBT = TreeNode('Drinks')
leftchild = TreeNode('Hot')
rightchild = TreeNode('Cold')
NewBT.leftchild = leftchild
NewBT.rightchild = rightchild

Pre-order: root -> left subtree-> right subtree

• Time complexity : O(n), Space complexity : O(n)

def PreOrderTraversal(rootNode):
  if not rootNode:
    return 
  print(rootNode.data)
  PreOrderTraversal(rootNode.leftchild)
  PreOrderTraversal(rootNode.rightchild)

PreOrderTraversal(NewBT)
# Output: Drinks -> Hot -> Cold

In-order: left subtree -> root -> right subtree

• Time complexity : O(n), Space complexity : O(n)

def InOrderTraversal(rootNode):
  if not rootNode:
    return
  InOrderTraversal(rootNode.leftchild)
  print(root.data)
  InOrderTraversal(rootNode.rightchild)
  
InOrderTraversal(NewBT)
# Output: Hot -> Drinks -> Cold

Post-order: left subtree -> right subtree -> root

• Time complexity : O(n), Space complexity : O(n)

def PostOrderTraversal(rootNode):
  if not rootNode:
    return 
  PostOrderTraversal(rootNode.leftchild)
  PostOrderTraversal(rootNode.rightchild)
  print(rootNode.data)

#add new child:
leftchild.leftchild = TreeNode('tea')
leftchild.rightchild = TreeNode('coffee')

PostOrderTraversal(NewBT)
# Output: tea -> coffee -> Hot -> Cold -> Drinks

Level-order: first level -> second level -> third level …

• Time complexity : O(n), Space complexity : O(n)

import QueueLinklisted as queue
 
def LevelOrderTraversal(rootNode):
  if not rootNode:
    return 
  else:
    customQueue = queue.Queue()
    customQueue.enqueue(rootNode)
    while not(customQueue.isEmpty()):
      root = customQueue.dequeue()
      print(root.value.data)
      if (root.value.leftchild is not None):
        customQueue.enqueue(root.value.leftchild)
      if (root.value.rightchild is not None):
        customQueue.enqueue(root.value.rightchild)

LevelOrderTraversal(NewBT)
# Output: Drinks -> Hot -> Cold -> tea -> coffee

# QueueLinklisted.py

class Node:
  def __init__(self, value = None):
    self.value = value
    self.next = None
  
  def __str__(self):
    return str(self.value)

class LinkedList:
  def __init__(self)
    self.head = None
    self.tail = None
  
  def __iter__(self):
    curNode = self.head
    while curNode:
      yield curNode
      curNode = curNode.next

class Queue:
  def __init__(self):
    self.linkedList = LinkedList()

  def __str__(self):
    values = [str(x) for x in self.linkedList]
    return ''.join(values)
  
  def enqueue(self, value):
    newNode = Node(value)
    if self.linkedList.head = None:
      self.linkedList.head = newNode
      self.linkedList.tail = newNode
    else:
      self.linkedList.tail.next = newNode
      self.linkedList.tail = newNode

  def isEmpty(self):
    if self.linkedList.head == None:
      return True
    else:
      return False

  def dequeue(self):
    if self.isEmpty():
      return "The Queue is empty."
    else:
      tempNode = self.linkedList.head
      if self.linkedList.head == self.linkedList.tail:
        self.linkedList.head, self.linkedList.tail = None, None
      else:
        self.linkedList.head = self.linkedList.head.next
      return tempNode
  
  def peek(self):
    if self.isEmpty():
          return "The Queue is empty."
    else:
      return self.linkedList.head
 
  def delete(self):
    self.linkedList.head, self.linkedList.tail = None, None