Master the Paths of Binary Tree Traversal Depth-First (DFS), Breadth-First (BFS) & Recursion

A Binary Tree is a hierarchical, non-linear data structure where each node has at most two children, referred to as the left child and the right child. Unlike linear structures (arrays, linked lists) which have a single logical way to iterate, trees can be traversed in several different ways.

Tree Traversal is the process of visiting every node in the tree exactly once. Traversals are generally divided into two main categories:

• Depth-First Search (DFS): Recursively explores paths as deep as possible before backtracking. Includes: Preorder, Inorder, and Postorder traversals.
• Breadth-First Search (BFS): Visits nodes level-by-level, starting from the root. Includes: Level-Order traversal.

In Preorder Traversal, the node is processed before (pre) traversing its left and right subtrees.

Preorder traversal is commonly used to create a copy of the tree or to serialize a expression tree structure into prefix notation.

function preorder(Node root)
    if root is null then return
    
    visit(root)
    preorder(root.left)
    preorder(root.right)
end function

In Inorder Traversal, the node is processed in-between (in) traversing its left and right subtrees.

In a Binary Search Tree (BST), executing an inorder traversal visits the nodes in **strictly ascending sorted order**. This is one of the most useful properties of BSTs.

function inorder(Node root)
    if root is null then return
    
    inorder(root.left)
    visit(root)
    inorder(root.right)
end function

In Postorder Traversal, the node is processed after (post) traversing both its left and right subtrees.

Postorder traversal is commonly used in deleting/freeing a tree (since you must delete children before deleting the parent) or for calculating the size/height of subtrees bottom-up.

function postorder(Node root)
    if root is null then return
    
    postorder(root.left)
    postorder(root.right)
    visit(root)
end function

Level-Order Traversal processes tree nodes layer-by-layer (horizontally), starting from level 0 (root), then level 1, and so on.

Since recursion uses a call stack (which behaves in a Depth-First manner), Level-Order traversal must be implemented iteratively using a **Queue data structure** (First-In, First-Out).

function levelOrder(Node root)
    if root is null then return
    
    Queue q = new Queue()
    q.enqueue(root)
    
    while q is not empty
        Node curr = q.dequeue()
        visit(curr)
        
        if curr.left is not null then
            q.enqueue(curr.left)
        end if
        if curr.right is not null then
            q.enqueue(curr.right)
        end if
    end while
end function

Below is a visual binary tree. Use it to trace the different path structures:

Analyze the binary trees described in the scenarios below to solve the traversal outputs.

Test your understanding of Binary Tree traversals: