Module 3 · Recursion, trees and the questions you cannot prepare for Lesson 9 of 15
Binary trees, traversals and search
Trees and their traversals — depth-first and breadth-first — cover a large share of second-round fresher questions.
The concept
A binary tree is a node with a left child, a right child, and a value. Traversals are just orders of visiting: pre-order is node, left, right; in-order is left, node, right and prints a binary SEARCH tree in sorted order; post-order is left, right, node and is how you free or compute upwards. Breadth-first uses a queue and goes level by level.
Three interview problems cover most of what is asked: how deep is the tree (recursion on both children, take the larger), is it balanced, and is a given tree a binary search tree (an in-order traversal comes out sorted). Search in a BST is a loop: go left if the target is smaller, right if larger, stop when you reach it.
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def depth(node):
if node is None: return 0
return 1 + max(depth(node.left), depth(node.right))
def inorder(node, out):
if node is None: return out
inorder(node.left, out); out.append(node.val); inorder(node.right, out)
return out
# In a binary SEARCH tree, the in-order traversal comes out sorted.Common mistakes
The mistake is writing a traversal that returns nothing because the recursive call was made without return. And on the BST question, checking only parent against child is not enough — the value must be inside an allowed RANGE from every ancestor, which is why in-order traversal is the safe answer.
Worked example
A breadth-first traversal with a queue prints level by level; depth-first with recursion prints all of one branch before the next. The output order is the difference, and interviewers ask for both.
Your practice task
Implement a tree insertion and all three depth-first traversals without looking anything up, then check against a written example.
Do this before moving on. Reading a solution teaches the shape of it; typing it teaches you.
Key takeaway
A binary tree is a node with a left child, a right child, and a value.
Keep your place in this course
A free account saves which lessons you have finished and unlocks the certificate. The lesson itself stays free to read.
Create free account or sign inCourse complete
You finished every lesson.
Your certificate is ready, and the projects you built are the proof to attach to an application.
Almost there
15 lessons left of 15
Finish every lesson to unlock the certificate. Each one ends in a practice task — do them and the final project brief writes itself.