DSA Basics: Trees

A tree is a hierarchical data structure made of nodes.

Each tree has a root node. Each node can have children. A node with no children is called a leaf.

        10
       /  \
      5    20
     / \     \
    3   7     30

Important terms

• Root: the top node.
• Parent: a node that points to children.
• Child: a node below another node.
• Leaf: a node with no children.
• Height: the longest path from a node to a leaf.

Traversal

Tree traversal means visiting every node in a planned order.

Depth-first traversal

Depth-first traversal goes down one branch before trying another.

• preorder: root, left, right
• inorder: left, root, right
• postorder: left, right, root

Breadth-first traversal

Breadth-first traversal visits level by level and usually uses a queue.

Recursive preorder example

function preorder(node) {
	if (!node) return;

	console.log(node.value);
	preorder(node.left);
	preorder(node.right);
}

Practice problems

1. Count nodes in a tree.
2. Find the maximum depth.
3. Invert a binary tree.
4. Check if two trees are the same.
5. Level-order traversal.

Practice links

• LeetCode Tree problems
• NeetCode practice roadmap