Given the root of a binary tree, return its maximum depth (the number of nodes on the longest path from the root to a leaf).

Recurse. An empty tree has depth 0. Otherwise the depth is 1 plus the larger of the depths of the left and right subtrees. Every node is visited once, so time is O(n). The recursion stack is O(h), where h is the height: O(log n) for a balanced tree and O(n) for a lopsided one.

Return the values of a binary tree level by level, as a list of lists.

Use a queue. Put the root in. While the queue is not empty, record how many nodes it holds (that is one level), take that many nodes out one at a time, add their values to the current level's list, and add each node's children to the queue. Time is O(n). Memory is O(w), where w is the widest level, up to about n / 2.

Given a binary tree and two nodes, find their lowest common ancestor, the deepest node that has both as descendants.

Recurse from the root. If the node is empty or is one of the two targets, return it. Otherwise search the left and right subtrees. If both return something, this node is the lowest common ancestor. If only one does, return that result upwards. Time is O(n) and the stack is O(h). If the tree is a binary search tree, you can instead walk down using the ordering in O(h).

Find the diameter of a binary tree, the length of the longest path between any two nodes.

For each node, the longest path with that node as the top is the height of its left subtree plus the height of its right subtree (in edges). Use a post-order recursion that returns the height of each subtree, and keep a running maximum of left + right at every node. The answer is that maximum. One pass visits each node once, so time is O(n) and the stack is O(h).

Trees

Hierarchies of nodes with one parent each. Learn binary trees and the four traversals, pre-order, in-order, post-order and level order.

beginner30 minAsked oftenTreesBinary treeTraversalRecursionHierarchy

Last reviewed 24 Oct 2026 · by TheLearningLoop Team

Read first: Data Structures & Algorithms: The Big Picture (blog post)

Progress is saved on this device. Create a free account to keep it everywhere.

On this page ▾

On this page

Key takeaways

A tree is nodes with one parent each and no cycles. A binary tree allows at most two children per node.
Pre-order, in-order and post-order go deep first. Level order goes one level at a time. All four visit each node once, so they take O(n).
Most tree problems have one shape: solve the left side, solve the right side, then combine the answers at the node.

When to use a tree

Use a tree when your data is a hierarchy:

One parent, many children: folders and files, an organisation chart, a menu, an HTML page.
A nested document such as JSON or XML.
Splitting a problem into smaller versions of itself, for example the choices in a game or a decision.
Ordered data that changes (a binary search tree), or priorities (a heap, which is a tree stored in an array).

Use something else when:

Items link to many others in any direction, or form loops: use a graph.
You need position access to a plain sequence: use an array.
You only look up exact keys: use a hash map.
You need fast sorted operations and the tree might become lopsided: use a balanced tree, not a plain binary tree.

Do not build general trees from scratch when a library has one. Many languages have sorted maps built on balanced trees, and the browser gives you the page as a tree. Writing a node class is for learning and interviews.

How a tree works

A tree is a set of nodes joined by edges with a root at the top.

Every node except the root has exactly one parent, and there are no cycles, so there is exactly one path from the root to any node.

Words you will meet:

Root: the top node. Leaf: a node with no children.
Parent and child: a node and the nodes directly below it.
Subtree: a node together with everything below it. Every subtree is a smaller tree.
Depth: how far a node is from the root. Height: the longest path from the root down to a leaf.

A binary tree is a tree where each node has at most two children, called left and right. A binary search tree is a binary tree with an ordering rule (see the Binary Search Tree lesson). A plain binary tree has no ordering rule.

Trees come in shapes. A balanced tree keeps its height close to log n. A lopsided (skewed) tree is more like a linked list, with height close to n. The height matters because most operations cost O(h).

Walking a tree: the four traversals

To traverse a tree is to visit every node once. There are four standard orders:

Order	Visits	Typical use
Pre-order	node, left, right	Copying a tree, printing a structure from the top
In-order	left, node, right	Reading a binary search tree in sorted order
Post-order	left, right, node	When a node needs its children's answers first: folder sizes, deleting a tree
Level order	top to bottom, left to right	Shortest steps, "by level" questions

The first three go deep first and use recursion (the call stack remembers the way back). Level order goes wide first and uses a queue.

Try it

Choose a traversal order and a tree, then step through. Watch the path from the root (or the queue) and the output so far.

Tree traversal

Step 1 of 27 · Press Space to play, arrow keys to step

Rule: left, node, right

Tree:

Path from the root: 1

Output so far: nothing yet

Go to the root to 1.

visited:: 0
depth:: 1
height:: 3

depth = how many nodes are on the path from the root to where we are. queue = nodes waiting in level order.

Speed

Things to try:

In-order on the Full tree: the output is 4, 2, 5, 1, 6, 3, 7. Then Pre-order: 1, 2, 4, 5, 3, 6, 7. Same tree, same nodes, different order, because the node is visited at a different moment.
Post-order on the full tree gives 4, 5, 2, 6, 7, 3, 1. The root comes last, because it waits for both children.
Pick the Lopsided tree and run In-order. The path grows to 4 nodes deep, as deep as the tree is tall. On a lopsided tree the recursion goes as deep as the number of nodes.
Level order uses a queue, not a path. Watch the queue hold one whole level at a time.

Tree operations: build, traverse and combine

Build. Each node stores a value and links to its left and right child (or none). A tree is just a link to its root.

Traverse. Write one function that handles one node and then calls itself on the left and right children. The only choice is when to visit the node relative to those two calls. A missing child (empty) is the base case that ends the recursion.

Combine. Most problems follow one shape: solve the left side, solve the right side, then combine the two answers at the current node. For example:

Height of a tree = 1 + the larger of the heights of the two children.
Number of nodes = 1 + nodes on the left + nodes on the right.
Total size of a folder = its own size + the sizes of its children.

Level order. Put the root in a queue. Repeatedly take the front node, visit it, and add its children to the back.

Interview fact. Every traversal visits each node once, so it takes O(n) time. The extra memory is O(h) for the recursive orders, where h is the height, and O(w) for level order, where w is the widest level.

Tree time complexity

Operation	Normal case	Worst case
Visit every node (any traversal)	O(n)	O(n)
Find a value in a tree with no ordering	O(n)	O(n)
Height, size, sum	O(n)	O(n)
Memory for pre, in or post-order	O(h)	O(n) for a lopsided tree
Memory for level order	O(w)	O(n)
Memory to store the tree	O(n)	O(n)

The height h is about log n for a balanced tree and n for a lopsided one, which is why balance matters.

Trees vs other data structures

The right choice depends on what you do most. n is the number of items.

What you need	Binary tree	Balanced search tree	Array or list	Graph
Model a hierarchy	Natural fit	Only if it is ordered	Awkward	Possible, but allows loops
Visit every item	O(n)	O(n)	O(n)	O(V + E)
Find a value (no ordering rule)	O(n)	Not applicable	O(n)	O(V + E)
Find a value (ordered keys)	O(n)	O(log n)	O(n), or O(log n) if sorted	O(V + E)
Items in sorted order	Only if built as a search tree	O(n) by in-order walk	O(n) if sorted	Not natural
Loops allowed	No	No	Not applicable	Yes

The bold cells show where each wins. A tree is the most natural fit for hierarchies, and a balanced search tree is the one to pick when you need fast ordered operations.

How to explain trees in an interview

Say the definition: "nodes with one parent each and no cycles, so one path from the root to any node."
Define height and say the cost in terms of it: "operations are O(h), which is log n if balanced and n if lopsided."
Name the traversal you will use and why: "post-order, because each node needs its children's answers first."
Write one recursive function and state what it returns, then say the base case for an empty node.
Say the memory: "O(h) for the recursion stack."

Where you meet trees in real systems

Any time data has a "contains" or "reports to" relationship, there is a tree. Here are three drawn out, the first with code you can run, then more examples.

Example 1: File systems

Your computer's folders are a tree: one root folder, and every file or folder sits inside exactly one parent. A question such as "how big is this folder?" is a post-order walk, because a folder cannot know its size until each of its children does. Open the example below to see the picture and the code.

Code: total the size of every folderTime O(n)Memory O(h)

The project folder holds src (65 KB, from main.py 40 and utils.py 25), docs (10 KB) and logo.png (125 KB), so its total is 200 KB. The folders are finished last, after all of their contents.

class Node:
    """A file or a folder. A file has a size. A folder has children.

    A file system is a tree: one root folder, and every file or folder has
    exactly one parent. Memory for the nodes: O(n) for n files and folders.
    """
    def __init__(self, name, size=0, children=None):
        self.name = name
        self.size = size                  # in KB; only files have a size of their own
        self.children = children or []    # empty for a file


def folder_sizes(node, report):
    """Return the total size of `node`, and record the total of every folder in `report`.

    This is a post-order traversal: finish all the children first, then use
    their answers to finish the parent.

    Time:   O(n). Every file and folder is visited exactly once.
    Memory: O(h) for the recursion stack, where h is the depth of the folder tree.
    """
    total = node.size
    for child in node.children:
        total += folder_sizes(child, report)   # children first...
    if node.children:
        report.append((node.name, total))      # ...then the folder itself
    return total

Each version built the same folder tree and printed 200 for the whole project, with the folder totals in finishing order: src 65, docs 10, project 200. All five were compiled and run, and none of them uses a package.

Example 2: Web pages and the DOM

A browser turns an HTML page into a tree called the DOM (Document Object Model). The html element is the root, and every element sits inside one parent. When you run document.querySelector or a CSS rule, the browser walks that tree. UI libraries such as React also describe screens as trees of components.

html is the root. It has two children, head and body. head holds a title. body holds a heading and a paragraph. Styles and scripts find elements by walking this tree.

Example 3: Expressions in compilers and calculators

When a compiler or a calculator reads 3 + 4 × 2, it builds an expression tree (a kind of abstract syntax tree). The operator is the node and the operands are its children. Because × binds tighter, it sits lower in the tree. Evaluating the tree is a post-order walk: work out the children first, then apply the operator.

Post-order evaluation: 4 × 2 = 8 first, because the × node sits below the +. Then 3 + 8 = 11. The shape of the tree encodes the order of operations, so no brackets are needed.

More real-world scenarios

4. Organisation charts, menus and nested documents

A reporting chart, a site's navigation menu and a JSON or XML document are all trees. Reading them is a traversal, and "show everyone under this manager" is a walk of a subtree.

5. Decision trees in machine learning

A decision tree model asks a yes or no question at each node, such as "is the age over 30?", and follows the left or right branch. A leaf holds the prediction. Predicting means walking from the root to one leaf, which takes O(h).

6. Game trees

Game-playing programs, for example for chess or noughts and crosses, represent moves as a tree: each node is a position and each child is a position reachable by one move. Search methods such as minimax walk this tree to choose a move.

7. Database indexes

Most database indexes are B-trees, a many-children relative of the binary search tree, so that finding a row, or a range of rows, takes only a few steps down a short tree. See the Binary Search Tree lesson for more.

8. Loop-free networks

The Spanning Tree Protocol used on Ethernet switches chooses a subset of links that forms a tree, so there is exactly one path between any two switches and frames cannot loop forever.

9. Heaps and priority queues

A heap is a binary tree where each parent is smaller than (or larger than) its children, usually stored in an array. It is the structure behind priority queues, such as "which job runs next?".

10. Git directories

Git stores each directory as a tree object that lists the files and sub-directories inside it. A commit points at the top tree, so a whole project snapshot is one tree.

Language standard libraries

Most languages do not ship a general-purpose tree class. They ship structures built on trees, and you write the node type yourself for plain binary trees.

Language	Structure or class	What it is under the hood	Notes
Java	`TreeMap`, `TreeSet`	Red-black (balanced search) tree	No general tree class: write a `Node` with left and right fields.
C++	`std::map`, `std::set`	Usually a red-black tree	Binary trees are normally written by hand with a `struct`.
C#	`SortedDictionary`, `SortedSet`	Red-black tree	Same as Java: write your own node class.
Rust	`BTreeMap`, `BTreeSet`	B-tree	A binary tree is usually `Option<Box<Node>>`.
Python	No general tree class	The `ast` module and `xml.etree.ElementTree` build trees you can walk	Write a small class for binary trees.
Go	No general tree class	Packages such as `go/ast` build trees for code	Use a struct with pointer fields.
JavaScript	The DOM	The browser's page tree, reached through `document`	`JSON.parse` returns a tree of nested objects and arrays.
Kotlin	`TreeMap`, `sortedSetOf`	Uses Java's red-black trees	Write your own node class for plain trees.

The pattern: sorted maps and sets are trees underneath, and documents like HTML and JSON are trees you walk. A plain binary tree is something you almost always write yourself.

The takeaway

Whenever a system has a hierarchy, or a problem that splits into smaller copies of itself, look for a tree. When items can link to many others or form loops, it usually uses a graph instead.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
Given the root of a binary tree, return its maximum depth (the number of nodes on the longest path from the root to a leaf).
easy
2.
Return the values of a binary tree level by level, as a list of lists.
medium
3.
Given a binary tree and two nodes, find their lowest common ancestor, the deepest node that has both as descendants.
medium
4.
Find the diameter of a binary tree, the length of the longest path between any two nodes.
medium

← Previous

Sorting and Binary Search

Binary Search Tree