Hackerrank In Top 30 MAANG Interview question — Tree Recursive Traversals

Here is the difference between preorder and the other DFS recursive traversals. On the following figure the nodes are numerated in the order you visit them, please follow 1-2-3-4-5 to compare different DFS strategies implemented as recursion.

• Time complexity: O(N) since one has to visit each node.
• Space complexity: up to O(H) to keep the recursion stack, where H is a tree height.

def preorder(r):
    if r:
        # process the root node
        print(r.val)
        preorder(r.left)
        preorder(r.right)
def inorder(r):
    if r:
        inorder(r.left)
        # process the root node
        print(r.val)
        inorder(r.right)
def postorder(r):
    if r:
        postorder(r.left)
        postorder(r.right)
        # process the root node
        print(r.val)
        

Implementations with Stack (iterative Solution):

1. Inorder traversal using stack https://leetcode.com/problems/binary-tree-inorder-traversal/submissions/

• First, append all nodes, and node’s left
• Next, check if the stack is empty, if yes, we break