Binary tree traversals

Abhishek Kumar • Category: Data Structures • Tags: datastructures binary-tree

Binary tree traversals can be done by Depth-first traversal and Breadth-first traversals or Level order traversal.
Preorder traversal, Inorder traversal and Postorder traversal are part of the Depth-first search.

Introduction to binary trees

Traversal of tree means visiting each node once in a tree data structure.

Traversal of other data structures like array, linked list are sequential i.e., a praticular sequence is defined but sequential traversal of tree is not possible.

Types of tree traversals

Following are the types of traversal of a binary tree.

Linked List node 
N – Root
L – Left
R – Right

These are the types of binary tree traversals

  1. Depth first traversal
    1. Preorder traversal
    2. Inorder traversal
    3. Postorder traversal
  2. Breadth first traversal / Level order traversal

These tree traversals are known as depth first traversal because these traversal algorithms traverse the deepest node first and nodes at same level later.

Linked List node
  1. Preorder (Root, Left, Right): 1, 2, 4, 5, 3, 6, 7
  2. Inorder (Left, Root, Right): 4, 2, 5, 1, 6, 3, 7
  3. Postorder (Left, Right, Root): 4, 5, 2, 6, 7, 3, 1

Level order traversal algorithm traverse the nodes at same level first and then traverse the nodes at next level.

Linked List node

Breadth first search / Level order traversal: 1, 2, 3, 4, 5, 6

Preorder traversal

  1. Print the data of the current node
  2. Traverse the left subtree
  3. Traverse the right subtree
Recursive 
def pre_order(root):
    if root:
        print(root.data)
        pre_order(root.left)
        pre_order(root.right)
function preOrder(root) {
  if (root) {
    console.log(root.data);
    preOrder(root.left);
    preOrder(root.right);
  }
}
Iterative

For iterative traversal we have to use an extra stack data structure.

def pre_order(root):
    if root:
        stack = []
        stack.append(root)
        while stack:
            node = stack.pop()
            print(node.data)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
function preOrder(root) {
  if (root) {
    const stack = [];
    stack.push(root);
    while (stack.length > 0) {
      node = stack.pop();
      console.log(node.data);
      if (node.right) {
        stack.push(node.right);
      }
      if (node.left) {
        stack.push(node.left);
      }
    }
  }
}

Inorder traversal

  1. Traverse the left subtree
  2. Print the data of the current node
  3. Traverse the right subtree
Recursive 
def in_order(root):
    if root:
        in_order(root.left)
        print(root.data)
        in_order(root.right)
function inOrder(root) {
  if (root) {
    inOrder(root.left);
    console.log(root.data);
    inOrder(root.right);
  }
}
Iterative

For iterative traversal we have to use an extra stack data structure.

def in_order(root):
    if root:
        stack = []
        node = root
        while stack or node:
            if node:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                print(node.data)
                node = node.right
function inOrder(root) {
  if (root) {
    const stack = [];
    node = root;
    while (stack.length > 0 || node) {
      if (node) {
        stack.push(node);
        node = node.left;
      } else {
        node = stack.pop();
        console.log(node.data);
        node = node.right;
      }
    }
  }
}

Postorder traversal

  1. Traverse the left subtree
  2. Traverse the right subtree
  3. Print the data of the current node
Recursive 
def post_order(root):
    if root:
        post_order(root.left)
        post_order(root.right)
        print(root.data)
function postOrder(root) {
  if (root) {
    postOrder(root.left);
    postOrder(root.right);
    console.log(root.data);
  }
}
Iterative

For iterative traversal we have to use an extra stack data structure.

def post_order(root):
    if root:
        visited = set()
        stack = []
        node = root
        while stack or node:
            if node:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                if node.right and not node.right in visited:
                    stack.append(node)
                    node = node.right
                else:
                    visited.add(node)
                    print(node.data)
                    node = None
function postOrder(root) {
  if (root) {
    const visited = new Set();
    const stack = [];
    node = root;
    while (stack.length > 0 || node) {
      if (node) {
        stack.push(node);
        node = node.left;
      } else {
        node = stack.pop();
        if (node.right && !visited.has(node.right)) {
          stack.push(node);
          node = node.right;
        } else {
          visited.add(node);
          console.log(node.data);
          node = null;
        }
      }
    }
  }
}

Level order traversal

In these kind of traversal, nodes of each level are traversed first and then next level will be traversed sequentially from left to right.

Recursive 
def level_order(root):
    h = height(root)
    for i in range(1, h+1):
        level_order_traverse(root, i)
  
def level_order_traverse(root , level):
    if root is None:
        return
    if level == 1:
        print(root.data)
    elif level > 1 :
        level_order_traverse(root.left , level-1)
        level_order_traverse(root.right , level-1)

def height(root):
    if root is None:
        return 0
    return max(height(root.left), height(root.right)) + 1
function levelOrder(root) {
  const h = height(root);
  for (let i = 1; i <= h; i++) {
    levelOrderTraverse(root, i);
  }
}

function levelOrderTraverse(root, level) {
  if (root == null) {
    return;
  }
  if (level == 1) {
    console.log(root.data);
  } else if (level > 1) {
    levelOrderTraverse(root.left, level - 1);
    levelOrderTraverse(root.right, level - 1);
  }
}

function height(root) {
  if (root == null) {
    return 0;
  }
  return Math.max(height(root.left), height(root.right)) + 1;
}
Iterative

For iterative traversal we have to use an extra queue data structure.

import queue           
def level_order(root):
    if root:
        q = queue.Queue()
        q.put(root)
        node = None

        while not q.empty():
            node = q.get()
            print(node.data)
            if node.left:
                q.put(node.left)
            if node.right:
                q.put(node.right)
function levelOrder(root) {
  if (root) {
    const q = [];
    q.push(root);
    node = null;

    while (q.length > 0) {
      node = q.shift();
      console.log(node.data);
      if (node.left) {
        q.push(node.left);
      }
      if (node.right) {
        q.push(node.right);
      }
    }
  }
}

Implementation of tree traversals

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

# pre order traversal
def pre_order(root):
    if root:
        print(root.data)
        pre_order(root.left)
        pre_order(root.right)

# in order traversal
def in_order(root):
    if root:
        in_order(root.left)
        print(root.data)
        in_order(root.right)

# post order traversal
def post_order(root):
    if root:
        post_order(root.left)
        post_order(root.right)
        print(root.data)

# level odrer traversal
def level_order(root):
    h = height(root)
    for i in range(1, h+1):
        level_order_traverse(root, i)
  
def level_order_traverse(root , level):
    if root is None:
        return
    if level == 1:
        print(root.data)
    elif level > 1 :
        level_order_traverse(root.left , level-1)
        level_order_traverse(root.right , level-1)

def height(root):
    if root is None:
        return 0
    return max(height(root.left), height(root.right)) + 1

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
class Node {
  constructor(data) {
    this.left = null;
    this.data = data;
    this.right = null;
  }
}

// pre order traversal
function preOrder(root) {
  if (root) {
    console.log(root.data);
    preOrder(root.left);
    preOrder(root.right);
  }
}

// in order traversal
function inOrder(root) {
  if (root) {
    inOrder(root.left);
    console.log(root.data);
    inOrder(root.right);
  }
}

// post order traversal
function postOrder(root) {
  if (root) {
    postOrder(root.left);
    postOrder(root.right);
    console.log(root.data);
  }
}

// level order traversal
function levelOrder(root) {
  const h = height(root);
  for (let i = 1; i <= h; i++) {
    levelOrderTraverse(root, i);
  }
}

function levelOrderTraverse(root, level) {
  if (root == null) {
    return;
  }
  if (level == 1) {
    console.log(root.data);
  } else if (level > 1) {
    levelOrderTraverse(root.left, level - 1);
    levelOrderTraverse(root.right, level - 1);
  }
}

function height(root) {
  if (root == null) {
    return 0;
  }
  return Math.max(height(root.left), height(root.right)) + 1;
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);

console.log("Pre order traversal");
preOrder(root);
console.log("nIn order traversal");
inOrder(root);
console.log("nPost order traversal");
postOrder(root);
console.log("nLevel order traversal");
levelOrder(root);

Output

Output

Pre order traversal
1
2
4
5
3
6
7

In order traversal  
4
2
5
1
6
3
7

Post order traversal
4
5
2
6
7
3
1

Level order traversal
1
2
3
4
5
6
7
Iterative 
class Node:
    def __init__(self, data):
        self.left = None
        self.data = data
        self.right = None

# pre order traversal
def pre_order(root):
    if root:
        stack = []
        stack.append(root)
        while stack:
            node = stack.pop()
            print(node.data)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)

# in order traversal
def in_order(root):
    if root:
        stack = []
        node = root
        while stack or node:
            if node:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                print(node.data)
                node = node.right

# post order traversal
def post_order(root):
    if root:
        visited = set()
        stack = []
        node = root
        while stack or node:
            if node:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                if node.right and not node.right in visited:
                    stack.append(node)
                    node = node.right
                else:
                    visited.add(node)
                    print(node.data)
                    node = None

# level odrer traversal
import queue           
def level_order(root):
    if root:
        q = queue.Queue()
        q.put(root)
        node = None

        while not q.empty():
            node = q.get()
            print(node.data)
            if node.left:
                q.put(node.left)
            if node.right:
                q.put(node.right)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

print('Pre order traversal')
pre_order(root)
print('\nIn order traversal')
in_order(root)
print('\nPost order traversal')
post_order(root)
print('\nLevel order traversal')
level_order(root)
class Node {
  constructor(data) {
    this.left = null;
    this.data = data;
    this.right = null;
  }
}

// pre order traversal
function preOrder(root) {
  if (root) {
    const stack = [];
    stack.push(root);
    while (stack.length > 0) {
      node = stack.pop();
      console.log(node.data);
      if (node.right) {
        stack.push(node.right);
      }
      if (node.left) {
        stack.push(node.left);
      }
    }
  }
}

// in order traversal
function inOrder(root) {
  if (root) {
    const stack = [];
    node = root;
    while (stack.length > 0 || node) {
      if (node) {
        stack.push(node);
        node = node.left;
      } else {
        node = stack.pop();
        console.log(node.data);
        node = node.right;
      }
    }
  }
}

// post order traversal
function postOrder(root) {
  if (root) {
    const visited = new Set();
    const stack = [];
    node = root;
    while (stack.length > 0 || node) {
      if (node) {
        stack.push(node);
        node = node.left;
      } else {
        node = stack.pop();
        if (node.right && !visited.has(node.right)) {
          stack.push(node);
          node = node.right;
        } else {
          visited.add(node);
          console.log(node.data);
          node = null;
        }
      }
    }
  }
}

// level order traversal
function levelOrder(root) {
  if (root) {
    const q = [];
    q.push(root);
    node = null;

    while (q.length > 0) {
      node = q.shift();
      console.log(node.data);
      if (node.left) {
        q.push(node.left);
      }
      if (node.right) {
        q.push(node.right);
      }
    }
  }
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);

console.log("Pre order traversal");
preOrder(root);
console.log("\nIn order traversal");
inOrder(root);
console.log("\nPost order traversal");
postOrder(root);
console.log("\nLevel order traversal");
levelOrder(root);

Output

Output

Pre order traversal
1
2
4
5
3
6
7

In order traversal  
4
2
5
1
6
3
7

Post order traversal
4
5
2
6
7
3
1

Level order traversal
1
2
3
4
5
6
7
«
Introduction to Binary Tree
Reverse level order traversal
»

AUTHOR

abhishek

Abhishek Kumar

Software engineer | Blogger | Keen learner
Python | Django | JavaScript | React | Next.js | Express.js | C
Passionate about learning and experimenting with new things and open to more opportunities and collaborations.

Recommended Posts -