Prerequisites :- Binary Trees.
Problem: Print nodes of given binary tree in preorder manner.
Solution Approach: Preorder traversal is one of the fundamental depth-first traversal methods for binary trees. In a binary tree, each node has at most two children: a left child and a right child. Preorder traversal follows the order of visiting nodes in the following sequence:
-
- Visit the Root Node:
- Start at the root of the tree.
- Process/visit the data (or perform an operation) associated with the root node.
- Visit the Root Node:
-
- Traverse the Left Subtree:
- Recursively perform a preorder traversal on the left subtree of the current node.
- For each node in the left subtree, repeat steps 1 and 2.
- Traverse the Left Subtree:
-
- Traverse the Right Subtree:
- Recursively perform a preorder traversal on the right subtree of the current node.
- For each node in the right subtree, repeat steps 1 and 2.
- Traverse the Right Subtree:
Time complexity: O(N), where N is the number of nodes in the tree. Each node is visited once.
Space complexity: O(1), as we don’t need any extra space.