Binary Tree Traversal, Height, BFS, DFS: Tutorial, Examples, FAQs & Interview Tips

Binary Tree Traversal, Height, BFS, DFS

Binary is a practical Data Structure topic that becomes clear when you connect the definition to a small working example.

Use this page to understand what happens, why it happens, how to verify it, and what mistake usually breaks the concept.

After reading, practice Binary with a normal case, a boundary case, and a broken case so the idea becomes usable instead of memorized.

Binary Tree Traversal Height BFS DFS should be studied as a practical Data Structure lesson, not as a label. Start by naming the input, the rule that changes the input, and the result a learner should be able to predict after reading the page.

In the data-structure > tree page, the notes should connect the definition with a working scenario, a mistake that beginners actually make, and the exact check that proves the fix. That makes the topic useful for coding, debugging, and interview revision.

What is a Tree?

A tree is a non-linear, hierarchical data structure consisting of nodes connected by edges. It has a root node at the top, and every node (except root) has exactly one parent. Trees are used everywhere - file systems, HTML DOM, databases, compilers, and more.

Tree Terminology

Term	Definition
Root	Top node with no parent
Leaf	Node with no children
Parent / Child	Direct connection between nodes
Sibling	Nodes sharing the same parent
Height	Longest path from root to a leaf
Depth	Distance from root to a node
Subtree	A node and all its descendants
Degree	Number of children a node has

Binary Tree - Traversals

A binary tree is a tree where each node has at most 2 children (left and right). The three main traversal orders are:

Inorder (L -> Root -> R) - gives sorted order for BST
Preorder (Root -> L -> R) - used to copy/serialize a tree
Postorder (L -> R -> Root) - used to delete a tree
Level-order (BFS) - visits level by level

Binary Tree - All Traversals

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

// Inorder: Left -> Root -> Right
void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

// Preorder: Root -> Left -> Right
void preorder(Node* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

// Postorder: Left -> Right -> Root
void postorder(Node* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

// Level-order (BFS)
void levelOrder(Node* root) {
    if (!root) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* node = q.front(); q.pop();
        cout << node->val << " ";
        if (node->left)  q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

// Height of tree
int height(Node* root) {
    if (!root) return 0;
    return 1 + max(height(root->left), height(root->right));
}

int main() {
    /*
     *       1
     *      / \
     *     2   3
     *    / \
     *   4   5
     */
    Node* 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);

    cout << "Inorder:    "; inorder(root);    cout << endl;  // 4 2 5 1 3
    cout << "Preorder:   "; preorder(root);   cout << endl;  // 1 2 4 5 3
    cout << "Postorder:  "; postorder(root);  cout << endl;  // 4 5 2 3 1
    cout << "LevelOrder: "; levelOrder(root); cout << endl;  // 1 2 3 4 5
    cout << "Height: " << height(root) << endl;  // 3
    return 0;
}

Binary Tree - Traversals

import java.util.*;

public class BinaryTree {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    static void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    static void preorder(Node root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }

    static void postorder(Node root) {
        if (root == null) return;
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.val + " ");
    }

    static void levelOrder(Node root) {
        if (root == null) return;
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            Node node = q.poll();
            System.out.print(node.val + " ");
            if (node.left  != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
    }

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

    public static void main(String[] args) {
        Node 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);

        System.out.print("Inorder: ");    inorder(root);    System.out.println();
        System.out.print("Preorder: ");   preorder(root);   System.out.println();
        System.out.print("Postorder: ");  postorder(root);  System.out.println();
        System.out.print("LevelOrder: "); levelOrder(root); System.out.println();
        System.out.println("Height: " + height(root));
    }
}

Binary Tree - Traversals

from collections import deque

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

def inorder(root):
    if not root: return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def preorder(root):
    if not root: return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def postorder(root):
    if not root: return []
    return postorder(root.left) + postorder(root.right) + [root.val]

def level_order(root):
    if not root: return []
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)
    return result

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

# Build tree:  1 / 2 3 / 4 5
root = Node(1)
root.left = Node(2); root.right = Node(3)
root.left.left = Node(4); root.left.right = Node(5)

print("Inorder:   ", inorder(root))      # [4, 2, 5, 1, 3]
print("Preorder:  ", preorder(root))     # [1, 2, 4, 5, 3]
print("Postorder: ", postorder(root))    # [4, 5, 2, 3, 1]
print("LevelOrder:", level_order(root))  # [1, 2, 3, 4, 5]
print("Height:    ", height(root))       # 3

Binary Tree - Traversals

class Node {
    constructor(val) { this.val = val; this.left = null; this.right = null; }
}

function inorder(root, result = []) {
    if (!root) return result;
    inorder(root.left, result);
    result.push(root.val);
    inorder(root.right, result);
    return result;
}

function preorder(root, result = []) {
    if (!root) return result;
    result.push(root.val);
    preorder(root.left, result);
    preorder(root.right, result);
    return result;
}

function postorder(root, result = []) {
    if (!root) return result;
    postorder(root.left, result);
    postorder(root.right, result);
    result.push(root.val);
    return result;
}

function levelOrder(root) {
    if (!root) return [];
    const result = [], queue = [root];
    while (queue.length) {
        const node = queue.shift();
        result.push(node.val);
        if (node.left)  queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    return result;
}

function height(root) {
    if (!root) return 0;
    return 1 + Math.max(height(root.left), height(root.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);

console.log("Inorder:   ", inorder(root));      // [4, 2, 5, 1, 3]
console.log("Preorder:  ", preorder(root));     // [1, 2, 4, 5, 3]
console.log("Postorder: ", postorder(root));    // [4, 5, 2, 3, 1]
console.log("LevelOrder:", levelOrder(root));   // [1, 2, 3, 4, 5]
console.log("Height:    ", height(root));       // 3

Deep Study Notes for Binary

Binary should be learned as a practical Data Structure skill, not only as a definition. Start by asking what problem the topic solves, what input or state it receives, what rule it applies, and what visible result proves it worked.

A strong explanation of Binary includes the normal case, a boundary case, and a failure case. When you practice, write down the before-state, the operation, the after-state, and the reason the result changed.

This lesson was expanded because the audit reported: limited checklist/practice/mistake/FAQ notes . The added notes below focus on clearer explanation, more examples, and concrete practice so the topic is easier to understand from the page itself.

Define the exact problem solved by Binary before looking at syntax.
Trace one small example by hand and describe every step in plain language.
Identify what changes when the input is empty, repeated, invalid, delayed, or larger than expected.
Connect the topic to a realistic project scenario instead of treating it as isolated theory.
Verify your answer with output, logs, query results, browser behavior, compiler feedback, or a state table.

Worked Explanation: Using Binary Correctly

Imagine you are adding Binary to a small learning project. The first step is to choose the smallest scenario that still shows the main idea. Avoid starting with a large production design; it hides the concept behind too many details.

Next, isolate the moving parts. Name the input, the rule, the output, and the possible error. This habit makes the topic easier to debug because you can see whether the problem is caused by bad data, wrong configuration, incorrect syntax, timing, permissions, or misunderstanding of the rule.

Finally, compare two versions: one correct version and one intentionally broken version. The broken version is valuable because it teaches you how the topic fails in real work, which is usually what interviews and debugging tasks test.

Normal case: show the expected behavior with simple, valid input.
Boundary case: test the smallest, largest, empty, repeated, or unusual value that still belongs to the topic.
Failure case: introduce one realistic mistake and explain the symptom it creates.
Repair step: change one thing at a time so you know exactly what fixed the problem.

Binary trace helper

def trace_binary(items):
    print('Input:', items)
    for index, value in enumerate(items):
        print(f'step={index}, value={value}, remaining={items[index+1:]}')
    return len(items)

print('operations:', trace_binary([4, 1, 7, 1]))

Binary edge-case practice

test_cases = [[], [5], [3, 3, 3], [9, -1, 0, 9]]
for case in test_cases:
    print('case:', case, 'size:', len(case))

# Explain the behavior for empty, single, repeated, and mixed data before optimizing.

Key Takeaways

State the purpose of Binary in one sentence before using it.
Create a tiny Data Structure example that demonstrates the topic without unrelated code.
Test one normal input, one edge input, and one incorrect input for Binary.
Explain the result using before-state, operation, and after-state.
Add a verification step such as output, logs, query results, browser behavior, or compiler feedback.

Common Mistakes to Avoid

WRONG Memorizing Binary as a definition only.

RIGHT Pair the definition with a small working example and a failure example.

The fastest way to remember the topic is to explain why the output changes.

WRONG Copying syntax without checking the state before and after.

RIGHT Write the input state, apply the rule, then inspect the output state.

State tracing turns confusing behavior into a visible sequence.

WRONG Ignoring the error path for Binary.

RIGHT Create one intentionally broken version and document the symptom and fix.

A page is much easier to learn from when it explains both success and failure.

WRONG Memorizing Binary Tree Traversal Height BFS DFS without the situation where it is useful.

RIGHT Connect Binary Tree Traversal Height BFS DFS to a concrete Data Structure task.

Purpose makes syntax easier to recall.

Practice Tasks

Build the smallest working demo for Binary and write what each line does.
Change one input or setting and predict the result before running it.
Break the example in a realistic way, then fix it and describe the repair.
Create a two-column note comparing when to use Binary and when another approach is better.
Explain Binary aloud as if teaching a beginner who knows basic Data Structure only.

Frequently Asked Questions

What should I understand first in Binary?

Understand the problem it solves, the input or state it works on, and the visible result that proves the concept is working.

How should I practice Binary?

Use one tiny correct example, one boundary example, and one broken example. Compare the output or state after each change.

Why do beginners struggle with Binary?

They often memorize the term without tracing the behavior. Tracing makes the rule easier to remember and debug.

What should I remember first about Binary Tree Traversal Height BFS DFS?

Remember the problem it solves in Data Structure, then attach the syntax or steps to that problem.

Previous Next

Binary Tree Traversal, Height, BFS, DFS: Tutorial, Examples, FAQs & Interview Tips