Tree Terminology and Traversal

A tree is a hierarchy: one root, parent-child relationships, and no cycles. That model powers folders, menus, comments, organization charts, DOM nodes, parsers, and many query planners.

Tree Language Engineers Use

A root has no parent. A leaf has no children. Depth counts distance from the root. Height counts the longest path down to a leaf. A subtree is a node plus everything below it. Clear terminology prevents confusion when algorithms recurse.

Scenario: Product Navigation Menu

A SaaS app has nested navigation: Workspace, Projects, Dashboards, Alerts, Billing. Rendering the menu is a traversal problem. Searching for a visible route may be DFS. Rendering by level or measuring breadth may be BFS.

Same Pattern in Java, Python, and JavaScript

Preorder traversal processes the current node before its children. It is natural for rendering, serialization, and command/menu trees.

import java.util.*;

class TreeNode {
    String value;
    List<TreeNode> children = new ArrayList<>();
}

class Preorder {
    static void visit(TreeNode node, List<String> out) {
        if (node == null) return;
        out.add(node.value);
        for (TreeNode child : node.children) visit(child, out);
    }
}

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Return the values of an n-ary tree level by level.
• Return the maximum depth of an n-ary tree.
• Serialize a nested menu tree so it can be stored and rebuilt later.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

import java.util.*;

class Node { String val; List<Node> children = new ArrayList<>(); }

class LevelOrderNary {
    static List<List<String>> levelOrder(Node root) {
        List<List<String>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<String> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                level.add(node.val);
                for (Node child : node.children) queue.offer(child);
            }
            result.add(level);
        }
        return result;
    }
}

import java.util.*;
class Node { List<Node> children = new ArrayList<>(); }
class NaryDepth { static int maxDepth(Node root) { if (root == null) return 0; int best = 0; for (Node child : root.children) best = Math.max(best, maxDepth(child)); return 1 + best; } }

import java.util.*;
class MenuNode { String id; List<MenuNode> children = new ArrayList<>(); }
class SerializeMenu { static void serialize(MenuNode node, List<String> out) { if (node == null) return; out.add(node.id + ":" + node.children.size()); for (MenuNode child : node.children) serialize(child, out); } }

Solved modelWorked Interview Answer

Return the level-order traversal of an n-ary tree. Level order is BFS. Use a queue because the next node to process is the oldest discovered node at the current frontier.

import java.util.*;

class Node { String val; List<Node> children = new ArrayList<>(); }

class LevelOrderNary {
    static List<List<String>> levelOrder(Node root) {
        List<List<String>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<String> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                level.add(node.val);
                for (Node child : node.children) queue.offer(child);
            }
            result.add(level);
        }
        return result;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Confusing depth and height.
• Using DFS when nearest-by-level is required.
• Assuming product data cannot contain cycles.
• Forgetting null/empty roots.
• Ignoring traversal order requirements.

Execution guardrailQuick-Start Checklist

• Name root and child relation.
• Choose DFS or BFS from the question.
• Handle empty tree.
• State time O(nodes).
• State recursion stack or queue memory.
• Mention visited set if data may be graph-like.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice n-ary tree preorder and level order.
• Review recursion and queues before tree traversal.
• Compare trees and graphs when cycles are possible.