Binary Tree Traversal, Height, BFS, DFS

Tree Relationships

A tree organizes nodes through parent-child relationships with one root and no cycles. Depth measures distance from the root, height measures the longest downward path, and a leaf has no children. State whether edge count or node count is used because textbook conventions differ.

Hierarchy, Not Sorting

General trees organize parent-child relationships. The main question is how nodes relate, not whether values are ordered.

Root has no parent.
Leaves have no children.
Subtrees repeat the same structure.

Tree Vocabulary

Depth, height, ancestor, descendant, sibling, and leaf are not decorative terms. They describe how algorithms move through the structure.

Depth counts from root to node.
Height counts the longest path downward.
A subtree can be processed like a smaller tree.

DFS and BFS Traversal

DFS explores branches deeply before moving across. BFS visits level by level. The traversal choice depends on the problem.

Use DFS for recursive structural work.
Use BFS for level order or nearest matching node.
Watch recursion depth in very deep trees.

Traversal Choice

Depth-first traversals use a stack through recursion or an explicit structure: preorder visits before children, postorder after children, and inorder is meaningful for ordered binary trees. Breadth-first traversal uses a queue and processes levels in order.

Every traversal is O(n) when it visits each node once, but auxiliary space depends on shape. A skewed recursive tree can exhaust the call stack; an explicit stack makes the resource visible. Define ownership and cleanup for dynamically allocated nodes.

Tree Representations

A general tree node can own a list of children. A binary tree stores at most left and right child links. An array representation is compact for complete binary trees such as heaps, while pointer or index links are more flexible for irregular hierarchies.

Representation	Strength	Cost
Child list	Natural for file or category hierarchies	Each node needs a variable-size collection.
Left and right links	Direct binary algorithms	Missing children still need null links.
Parent array	Compact ancestry queries	Child lookup needs another index or scan.
Level-order array	Excellent for complete trees	Sparse shapes waste positions.

Height and Complexity

Traversal work is proportional to visited nodes, but height controls recursion depth and many path operations. A balanced binary tree with n nodes has logarithmic height; a one-child chain has linear height.

Do not confuse a tree with a graph that merely looks hierarchical. A valid rooted tree has one path from the root to each node. Import code should detect cycles, missing parents, and nodes with multiple parents when those states violate the model.

Preorder is useful for copying or serializing a hierarchy before its descendants.
Postorder is useful when children must be processed or freed before a parent.
BFS finds minimum edge distance from the root in an unweighted tree.
Inorder has ordering meaning only when the binary tree carries an ordering invariant.

Category Tree Traversal

Electronics
  Computers
    Laptops
    Monitors
  Audio
    Headphones

DFS reads down a branch. BFS reads level by level.

Compute Tree Height Recursively

Height follows the hierarchy and does not depend on key ordering.

Compute Tree Height Recursively

function height(node) {
  if (!node) return 0;
  return 1 + Math.max(...node.children.map(height), 0);
}
const tree = { value:'root', children:[
  { value:'docs', children:[{ value:'api', children:[] }] },
  { value:'src', children:[] }
]};
console.log(height(tree));

Output

This definition counts nodes; an edge-based definition would return 2.

Before you move on

Tree Model Review

5 checks

Explain root, leaf, depth, and height.
Choose DFS or BFS based on the task.
Recognize that a tree does not have to be sorted.
Choose a representation that matches the expected shape.
Account for traversal time and auxiliary space.

Tree Reasoning Errors

Height convention is unstated
State whether height counts edges or nodes and use it consistently.
Recursive DFS on an extreme chain
Use an explicit stack or establish a safe depth bound.
Inorder assumed sorted
Require a BST ordering invariant before making that claim.

Tree Data Structure Questions Learners Ask

No. A BST is a specific ordered binary tree. Many trees are not ordered at all.

Previous Next

Binary Tree Traversal, Height, BFS, DFS

Tree Relationships

Hierarchy, Not Sorting

Tree Vocabulary

DFS and BFS Traversal

Traversal Choice

Tree Representations

Height and Complexity

Category Tree Traversal

Compute Tree Height Recursively

Tree Model Review

Tree Reasoning Errors

Height convention is unstated

Recursive DFS on an extreme chain

Inorder assumed sorted

Tree Connections

Tree Data Structure Questions Learners Ask

Is every tree a BST?

Tree Data Structure Resources

Popular Tutorials