Trees are one of the most important data structures for coding interviews. They appear in about 20-25% of all interview questions at top tech companies. If you are comfortable with trees, you have a big advantage. In this article, you will learn binary trees, tree traversals, and binary search trees (BST).
We show every example in Kotlin, Python, and Go.
What is a Tree?
A tree is a hierarchical data structure made of nodes connected by edges. It looks like an upside-down tree — the root is at the top, and the leaves are at the bottom.
Key terms:
- Root: the top node (no parent)
- Leaf: a node with no children
- Edge: the connection between two nodes
- Parent: the node directly above
- Child: the node directly below
- Height: the longest path from the root to a leaf
- Depth: the distance from the root to a node
Binary Tree
A binary tree is a tree where each node has at most two children — a left child and a right child.
Node Definition
Kotlin:
class TreeNode(
var value: Int,
var left: TreeNode? = null,
var right: TreeNode? = null
)
Python:
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
Go:
type TreeNode struct {
Value int
Left *TreeNode
Right *TreeNode
}
Building a Tree
Let’s build this tree for our examples:
1
/ \
2 3
/ \ \
4 5 6
Kotlin:
val root = TreeNode(1).apply {
left = TreeNode(2).apply {
left = TreeNode(4)
right = TreeNode(5)
}
right = TreeNode(3).apply {
right = TreeNode(6)
}
}
Python:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
Go:
root := &TreeNode{
Value: 1,
Left: &TreeNode{
Value: 2,
Left: &TreeNode{Value: 4},
Right: &TreeNode{Value: 5},
},
Right: &TreeNode{
Value: 3,
Right: &TreeNode{Value: 6},
},
}
Tree Traversals
Traversal means visiting every node in the tree. There are four common ways to traverse a binary tree. The first three are depth-first (DFS), and the last one is breadth-first (BFS).
Inorder Traversal (Left, Root, Right)
Visit the left subtree first, then the root, then the right subtree. For a BST, inorder traversal gives you the elements in sorted order.
For our example tree: 4, 2, 5, 1, 3, 6
Kotlin:
fun inorder(root: TreeNode?) {
if (root == null) return
inorder(root.left)
print("${root.value} ")
inorder(root.right)
}
Python:
def inorder(root):
if root is None:
return
inorder(root.left)
print(root.value, end=" ")
inorder(root.right)
Go:
func inorder(root *TreeNode) {
if root == nil {
return
}
inorder(root.Left)
fmt.Printf("%d ", root.Value)
inorder(root.Right)
}
Preorder Traversal (Root, Left, Right)
Visit the root first, then the left subtree, then the right subtree. Preorder is useful for creating a copy of the tree.
For our example tree: 1, 2, 4, 5, 3, 6
Kotlin:
fun preorder(root: TreeNode?) {
if (root == null) return
print("${root.value} ")
preorder(root.left)
preorder(root.right)
}
Python:
def preorder(root):
if root is None:
return
print(root.value, end=" ")
preorder(root.left)
preorder(root.right)
Go:
func preorder(root *TreeNode) {
if root == nil {
return
}
fmt.Printf("%d ", root.Value)
preorder(root.Left)
preorder(root.Right)
}
Postorder Traversal (Left, Right, Root)
Visit the left subtree, then the right subtree, then the root. Postorder is useful for deleting a tree (delete children before the parent).
For our example tree: 4, 5, 2, 6, 3, 1
Kotlin:
fun postorder(root: TreeNode?) {
if (root == null) return
postorder(root.left)
postorder(root.right)
print("${root.value} ")
}
Python:
def postorder(root):
if root is None:
return
postorder(root.left)
postorder(root.right)
print(root.value, end=" ")
Go:
func postorder(root *TreeNode) {
if root == nil {
return
}
postorder(root.Left)
postorder(root.Right)
fmt.Printf("%d ", root.Value)
}
Level-Order Traversal (BFS)
Visit nodes level by level, from left to right. Use a queue to process nodes in order.
For our example tree: 1, 2, 3, 4, 5, 6
Kotlin:
fun levelOrder(root: TreeNode?): List<List<Int>> {
if (root == null) return emptyList()
val result = mutableListOf<List<Int>>()
val queue: java.util.Queue<TreeNode> = java.util.LinkedList()
queue.add(root)
while (queue.isNotEmpty()) {
val level = mutableListOf<Int>()
val size = queue.size
for (i in 0 until size) {
val node = queue.poll()
level.add(node.value)
node.left?.let { queue.add(it) }
node.right?.let { queue.add(it) }
}
result.add(level)
}
return result
}
Python:
from collections import deque
def level_order(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
Go:
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
var result [][]int
queue := []*TreeNode{root}
for len(queue) > 0 {
size := len(queue)
level := make([]int, 0, size)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Value)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
result = append(result, level)
}
return result
}
Maximum Depth of Binary Tree
Find the maximum depth (height) of a binary tree. This is a classic recursive problem.
Kotlin:
fun maxDepth(root: TreeNode?): Int {
if (root == null) return 0
val leftDepth = maxDepth(root.left)
val rightDepth = maxDepth(root.right)
return maxOf(leftDepth, rightDepth) + 1
}
Python:
def max_depth(root):
if root is None:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return max(left_depth, right_depth) + 1
Go:
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
leftDepth := maxDepth(root.Left)
rightDepth := maxDepth(root.Right)
if leftDepth > rightDepth {
return leftDepth + 1
}
return rightDepth + 1
}
Time complexity: O(n) — visit every node once. Space complexity: O(h) where h is the height of the tree (recursion stack).
Invert Binary Tree
Swap the left and right children of every node. This is the famous problem that Homebrew’s creator Max Howell could not solve in a Google interview.
Kotlin:
fun invertTree(root: TreeNode?): TreeNode? {
if (root == null) return null
val temp = root.left
root.left = invertTree(root.right)
root.right = invertTree(temp)
return root
}
Python:
def invert_tree(root):
if root is None:
return None
root.left, root.right = invert_tree(root.right), invert_tree(root.left)
return root
Go:
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}
Binary Search Tree (BST)
A binary search tree is a binary tree with one extra rule: for every node, all values in the left subtree are smaller and all values in the right subtree are larger.
This rule gives us efficient searching. Instead of checking every node, we can go left or right based on the value we are looking for. This cuts the search space in half at each step.
8
/ \
3 10
/ \ \
1 6 14
BST Search
Kotlin:
fun search(root: TreeNode?, target: Int): TreeNode? {
if (root == null || root.value == target) return root
return if (target < root.value) {
search(root.left, target)
} else {
search(root.right, target)
}
}
Python:
def search(root, target):
if root is None or root.value == target:
return root
if target < root.value:
return search(root.left, target)
return search(root.right, target)
Go:
func search(root *TreeNode, target int) *TreeNode {
if root == nil || root.Value == target {
return root
}
if target < root.Value {
return search(root.Left, target)
}
return search(root.Right, target)
}
Time complexity: O(log n) average for a balanced BST. O(n) worst case for a skewed tree (like a linked list).
BST Insert
To insert a value, walk down the tree using the BST rule. When you reach a null position, that is where the new node goes.
Kotlin:
fun insert(root: TreeNode?, value: Int): TreeNode {
if (root == null) return TreeNode(value)
if (value < root.value) {
root.left = insert(root.left, value)
} else {
root.right = insert(root.right, value)
}
return root
}
Python:
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
Go:
func insert(root *TreeNode, value int) *TreeNode {
if root == nil {
return &TreeNode{Value: value}
}
if value < root.Value {
root.Left = insert(root.Left, value)
} else {
root.Right = insert(root.Right, value)
}
return root
}
Validate BST
Given a binary tree, check if it is a valid BST. A common mistake is to only check that the left child is smaller and the right child is larger. You must check that all nodes in the left subtree are smaller and all nodes in the right subtree are larger.
The trick: pass down the valid range (min, max) at each node.
Kotlin:
fun isValidBST(root: TreeNode?): Boolean {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE)
}
fun validate(node: TreeNode?, min: Long, max: Long): Boolean {
if (node == null) return true
if (node.value <= min || node.value >= max) return false
return validate(node.left, min, node.value.toLong()) &&
validate(node.right, node.value.toLong(), max)
}
Python:
def is_valid_bst(root):
def validate(node, min_val, max_val):
if node is None:
return True
if node.value <= min_val or node.value >= max_val:
return False
return (validate(node.left, min_val, node.value) and
validate(node.right, node.value, max_val))
return validate(root, float('-inf'), float('inf'))
Go:
func isValidBST(root *TreeNode) bool {
return validate(root, nil, nil)
}
func validate(node *TreeNode, min, max *int) bool {
if node == nil {
return true
}
if (min != nil && node.Value <= *min) ||
(max != nil && node.Value >= *max) {
return false
}
return validate(node.Left, min, &node.Value) &&
validate(node.Right, &node.Value, max)
}
Time complexity: O(n). Space complexity: O(h) for recursion stack.
Balanced vs Unbalanced BST
A balanced BST has roughly equal numbers of nodes on the left and right sides. Operations take O(log n). An unbalanced BST can degrade to a linked list where operations take O(n).
Balanced: Unbalanced (skewed):
4 1
/ \ \
2 6 2
/ \ / \ \
1 3 5 7 3
\
4
Self-balancing trees like AVL trees and Red-Black trees automatically maintain balance. In most languages, the built-in sorted map uses a Red-Black tree — for example, TreeMap in Kotlin/Java. Python’s standard library does not have a built-in sorted map; you need the third-party sortedcontainers library for SortedDict, or use bisect with a list for simple cases.
Why Interviewers Ask Tree Questions
Tree questions test:
- Recursive thinking — most tree solutions are naturally recursive
- Understanding of DFS vs BFS — choosing the right traversal method
- Edge case handling — null nodes, single-node trees, unbalanced trees
- Space complexity awareness — the recursion stack uses O(h) space
Practice Problems
Try these problems on LeetCode:
- Maximum Depth of Binary Tree (LeetCode #104) — basic recursion
- Invert Binary Tree (LeetCode #226) — swap children recursively
- Validate Binary Search Tree (LeetCode #98) — pass min/max range
- Binary Tree Level Order Traversal (LeetCode #102) — BFS with queue
- Lowest Common Ancestor of BST (LeetCode #235) — use BST property
What’s Next?
In the next article, we cover Heaps and Priority Queues — data structures that always give you the minimum or maximum element in O(1) time. Heaps power many important algorithms including Dijkstra’s shortest path and the top-K pattern.
Next: DSA Tutorial #6: Heaps and Priority Queues
Full series: DSA from Zero to Interview Ready