L5. Preorder Traversal of Binary Tree | C++ | Java | Code Explanation

Education

L5. Preorder Traversal of Binary Tree | C++ | Java | Code Explanation

Before diving into the main content of this article, I would like to extend my gratitude to Relevel for sponsoring this entire video. Relevel, by Unacademy, is a hiring platform that requires no degree or prior experience. They offer mentoring sessions and job opportunities in front-end, back-end, and business development from top Indian companies, all for free. The entire hiring process is swift and simple—just give the relevant test, and based on your score, interviews will be scheduled and you'll get hired. Check out the links in the description and apply for the relevant tests as soon as possible.

Preorder Traversal of Binary Tree

In this lecture, we will explore the coding implementation of the pre-order traversal technique in binary trees. We have previously discussed DFS traversal methods, that include pre-order, in-order, and post-order traversals. Here, we focus specifically on pre-order traversal.

Preorder Traversal Explained

In preorder traversal, the sequence of visiting nodes is:

  1. Root
  2. Left
  3. Right

Let's implement a simple and intuitive approach to writing the preorder traversal code. The steps are straightforward:

  1. Visit the root node and print it.
  2. Recurse on the left subtree.
  3. Recurse on the right subtree.

Here is the C++/Java code for preorder traversal:

void preorder(Node* root) (
    if(root == nullptr) return; // base case
    cout << root->data << " "; // visit the root
    preorder(root->left); // recur on the left subtree
    preorder(root->right); // recur on the right subtree
)

Dry Run of Preorder Traversal

Consider the following example tree for a step-by-step dry run:

      1
     / \
    2   3
   / \   \
  4   5   7
     /     \
    6       8
              \
               9
                \
                10

Starting at the root node (1):

  • Print 1 (root)
  • Move to the left subtree and call preorder on node 2:
    • Print 2 (root)
    • Move to the left subtree and call preorder on node 4:
      • Print 4 (root)
      • Both left and right of 4 are null, return to 2
    • Move to the right subtree and call preorder on node 5:
      • Print 5 (root)
      • Recur on left subtree, output is 6, right is null. So output sequence is 4, 2, 5, 6
  • Move to the right subtree and call preorder on node 3:
    • Print 3 (root)
    • Move to left, output is 7,
    • Move to right and call preorder on node 8 (continuing in depth-first manner):
      • Print 8 (root)
      • Move left, print 9, move right print 10.
    • Combining, the final preorder traversal sequence is 1, 2, 4, 5, 6, 3, 7, 8, 9, 10.

Time and Space Complexity

  • Time Complexity: (O(n)), where (n) is the number of nodes in the tree, because each node is visited once.
  • Space Complexity: The auxiliary space used in the recursive stack is (O(h)), where (h) is the height of the tree. In the worst case, this can be (O(n)) for a completely skewed tree.

Keywords

  • Preorder Traversal
  • Binary Tree
  • DFS (Depth-First Search)
  • C++ Code
  • Java Code
  • Time Complexity
  • Space Complexity
  • Recursive Implementation

FAQ

1. What is preorder traversal in a binary tree?

Preorder traversal in a binary tree is a depth-first search (DFS) technique where the nodes are recursively visited in this order: Root, Left subtree, Right subtree.

2. What is the time complexity of preorder traversal?

The time complexity of preorder traversal is (O(n)), where (n) is the number of nodes in the binary tree.

3. What is the space complexity of preorder traversal?

The space complexity of preorder traversal is (O(h)), where (h) is the height of the tree. In the worst-case scenario, the space complexity is (O(n)), especially for a completely skewed tree.

4. Can preorder traversal be implemented iteratively?

Yes, preorder traversal can be implemented iteratively using a stack to simulate the recursive call stack.

5. Why is preorder traversal useful?

Preorder traversal is useful for creating a copy of the tree, for prefix expression evaluation, and for various tree-based algorithms where the root node needs to be processed before its child nodes.