You already know the traversals and height(). This topic is the problem toolkit for binary trees: level-by-level BFS, horizontal distances, the return height, record the answer on the side pattern, two-stack tricks and (de)serialisation — the handful of techniques behind almost every tree interview question.
10
/ \
20 30
/ \ / \
40 50 60 70
/ \
80 90Conventions used in these notes
| Term | Meaning here | Sample tree |
|---|---|---|
| Height | number of nodes on the longest root-to-leaf path; an empty tree has height 0 | 4 (10 → 30 → 70 → 80) |
| Level | root is level 0, its children level 1, … | 4 levels (0–3) |
| Diameter | number of nodes on the longest path between any two nodes | 6 (40 20 10 30 70 80) |
| Horizontal distance (hd) | root 0; a left child is hd − 1, a right child hd + 1 | 40 is at −2, 90 at +3 |
| Balanced | for every node, |height(left) − height(right)| ≤ 1 | yes |
| Complete | all levels full except possibly the last, which is filled left to right | no (gap under 40/50/60) |
Node class and the sample tree
Every program in this topic starts with the same Node class and a sample() builder that constructs the tree above by nesting constructor calls. Here it is with three warm-ups you already know: inorder, height and node count.
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample(): # the tree used throughout these notes
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def inorder(n):
if n is None:
return
inorder(n.left)
print(n.key, end=" ")
inorder(n.right)
def height(n): # in nodes: a single node has height 1
if n is None:
return 0
return 1 + max(height(n.left), height(n.right))
def count_nodes(n):
return 0 if n is None else 1 + count_nodes(n.left) + count_nodes(n.right)
root = sample()
print("inorder:", end=" "); inorder(root); print()
print("height:", height(root))
print("nodes:", count_nodes(root))#include <iostream>
#include <algorithm>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() { // the tree used throughout these notes
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
void inorder(Node* n) {
if (!n) return;
inorder(n->left);
cout << n->key << " ";
inorder(n->right);
}
int height(Node* n) { // in nodes: a single node has height 1
if (!n) return 0;
return 1 + max(height(n->left), height(n->right));
}
int countNodes(Node* n) { return n ? 1 + countNodes(n->left) + countNodes(n->right) : 0; }
int main() {
Node* root = sample();
cout << "inorder: "; inorder(root); cout << "\n";
cout << "height: " << height(root) << "\n";
cout << "nodes: " << countNodes(root) << "\n";
}public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() { // the tree used throughout these notes
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static void inorder(Node n) {
if (n == null) return;
inorder(n.left);
System.out.print(n.key + " ");
inorder(n.right);
}
static int height(Node n) { // in nodes: a single node has height 1
if (n == null) return 0;
return 1 + Math.max(height(n.left), height(n.right));
}
static int countNodes(Node n) { return n == null ? 0 : 1 + countNodes(n.left) + countNodes(n.right); }
public static void main(String[] args) {
Node root = sample();
System.out.print("inorder: "); inorder(root); System.out.println();
System.out.println("height: " + height(root));
System.out.println("nodes: " + countNodes(root));
}
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () => // the tree used throughout these notes
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function inorder(n) {
if (!n) return;
inorder(n.left);
process.stdout.write(n.key + " ");
inorder(n.right);
}
function height(n) { // in nodes: a single node has height 1
return n ? 1 + Math.max(height(n.left), height(n.right)) : 0;
}
const countNodes = n => n ? 1 + countNodes(n.left) + countNodes(n.right) : 0;
const root = sample();
process.stdout.write("inorder: "); inorder(root); console.log();
console.log("height:", height(root));
console.log("nodes:", countNodes(root));inorder: 40 20 50 10 60 30 80 70 90
height: 4
nodes: 9The technique toolbox
Almost every problem below is one of five patterns. Recognise the pattern and the code writes itself.
Level order traversal line by line
Plain BFS prints all keys on one line. To start a new line after every level you need to know where a level ends. There are two classic ways.
from collections import deque
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def print_levels(root):
if root is None:
return
q = deque([root, None]) # None marks the end of a level
while len(q) > 1: # only the marker left → done
curr = q.popleft()
if curr is None:
print() # level finished: newline, re-arm the marker
q.append(None)
continue
print(curr.key, end=" ")
if curr.left:
q.append(curr.left)
if curr.right:
q.append(curr.right)
print()
print_levels(sample())#include <iostream>
#include <queue>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
void printLevels(Node* root) {
if (!root) return;
queue<Node*> q;
q.push(root);
q.push(nullptr); // nullptr marks the end of a level
while (q.size() > 1) { // only the marker left → done
Node* curr = q.front(); q.pop();
if (!curr) {
cout << "\n"; // level finished: newline, re-arm the marker
q.push(nullptr);
continue;
}
cout << curr->key << " ";
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
cout << "\n";
}
int main() { printLevels(sample()); }import java.util.LinkedList;
import java.util.Queue;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static void printLevels(Node root) {
if (root == null) return;
Queue<Node> q = new LinkedList<>(); // ArrayDeque would reject the null marker
q.add(root);
q.add(null); // null marks the end of a level
while (q.size() > 1) { // only the marker left → done
Node curr = q.poll();
if (curr == null) {
System.out.println(); // level finished: newline, re-arm the marker
q.add(null);
continue;
}
System.out.print(curr.key + " ");
if (curr.left != null) q.add(curr.left);
if (curr.right != null) q.add(curr.right);
}
System.out.println();
}
public static void main(String[] args) { printLevels(sample()); }
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function printLevels(root) {
if (!root) return;
const q = [root, null]; // null marks the end of a level
while (q.length > 1) { // only the marker left → done
const curr = q.shift();
if (curr === null) {
console.log(); // level finished: newline, re-arm the marker
q.push(null);
continue;
}
process.stdout.write(curr.key + " ");
if (curr.left) q.push(curr.left);
if (curr.right) q.push(curr.right);
}
console.log();
}
printLevels(sample());10
20 30
40 50 60 70
80 90Time O(n) · Space O(w) — w = maximum width
from collections import deque
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def print_levels(root):
if root is None:
return
q = deque([root])
while q:
for _ in range(len(q)): # exactly the nodes of this level
curr = q.popleft()
print(curr.key, end=" ")
if curr.left:
q.append(curr.left)
if curr.right:
q.append(curr.right)
print() # level done
print_levels(sample())#include <iostream>
#include <queue>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
void printLevels(Node* root) {
if (!root) return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int count = q.size(); // exactly the nodes of this level
for (int i = 0; i < count; i++) {
Node* curr = q.front(); q.pop();
cout << curr->key << " ";
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
cout << "\n"; // level done
}
}
int main() { printLevels(sample()); }import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static void printLevels(Node root) {
if (root == null) return;
Queue<Node> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
int count = q.size(); // exactly the nodes of this level
for (int i = 0; i < count; i++) {
Node curr = q.poll();
System.out.print(curr.key + " ");
if (curr.left != null) q.add(curr.left);
if (curr.right != null) q.add(curr.right);
}
System.out.println(); // level done
}
}
public static void main(String[] args) { printLevels(sample()); }
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function printLevels(root) {
if (!root) return;
const q = [root];
while (q.length) {
const count = q.length; // exactly the nodes of this level
const line = [];
for (let i = 0; i < count; i++) {
const curr = q.shift();
line.push(curr.key);
if (curr.left) q.push(curr.left);
if (curr.right) q.push(curr.right);
}
console.log(line.join(" ")); // level done
}
}
printLevels(sample());10
20 30
40 50 60 70
80 90Time O(n) · Space O(w)
Check for balanced binary tree
balanced (Yes) not balanced (No)
10 10
/ \ / \
20 30 20 30 ← left height 1,
/ \ / \ / \ / \ right height 3
40 50 60 70 40 50 60 70
/ \ / \
80 90 80 90
/
100class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def height(n):
return 0 if n is None else 1 + max(height(n.left), height(n.right))
def is_balanced(n):
if n is None:
return True
lh, rh = height(n.left), height(n.right) # O(n) each, for every node
return abs(lh - rh) <= 1 and is_balanced(n.left) and is_balanced(n.right)
root = sample()
print("sample tree:", "Yes" if is_balanced(root) else "No")
root.right.right.left.left = Node(100) # hang 100 under 80
print("with 100 under 80:", "Yes" if is_balanced(root) else "No")#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
int height(Node* n) { return n ? 1 + max(height(n->left), height(n->right)) : 0; }
bool isBalanced(Node* n) {
if (!n) return true;
int lh = height(n->left), rh = height(n->right); // O(n) each, for every node
return abs(lh - rh) <= 1 && isBalanced(n->left) && isBalanced(n->right);
}
int main() {
Node* root = sample();
cout << "sample tree: " << (isBalanced(root) ? "Yes" : "No") << "\n";
root->right->right->left->left = new Node(100); // hang 100 under 80
cout << "with 100 under 80: " << (isBalanced(root) ? "Yes" : "No") << "\n";
}public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static int height(Node n) { return n == null ? 0 : 1 + Math.max(height(n.left), height(n.right)); }
static boolean isBalanced(Node n) {
if (n == null) return true;
int lh = height(n.left), rh = height(n.right); // O(n) each, for every node
return Math.abs(lh - rh) <= 1 && isBalanced(n.left) && isBalanced(n.right);
}
public static void main(String[] args) {
Node root = sample();
System.out.println("sample tree: " + (isBalanced(root) ? "Yes" : "No"));
root.right.right.left.left = new Node(100); // hang 100 under 80
System.out.println("with 100 under 80: " + (isBalanced(root) ? "Yes" : "No"));
}
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
const height = n => n ? 1 + Math.max(height(n.left), height(n.right)) : 0;
function isBalanced(n) {
if (!n) return true;
const lh = height(n.left), rh = height(n.right); // O(n) each, for every node
return Math.abs(lh - rh) <= 1 && isBalanced(n.left) && isBalanced(n.right);
}
const root = sample();
console.log("sample tree:", isBalanced(root) ? "Yes" : "No");
root.right.right.left.left = new Node(100); // hang 100 under 80
console.log("with 100 under 80:", isBalanced(root) ? "Yes" : "No");sample tree: Yes
with 100 under 80: NoTime O(n · h) — O(n²) when skewed · Space O(h) recursion
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def check(n): # height of n, or -1 if the subtree is unbalanced
if n is None:
return 0
lh = check(n.left)
if lh == -1:
return -1 # short-circuit: no need to look at the right side
rh = check(n.right)
if rh == -1 or abs(lh - rh) > 1:
return -1
return 1 + max(lh, rh)
def is_balanced(root):
return check(root) != -1
root = sample()
print("sample tree:", "Yes" if is_balanced(root) else "No")
root.right.right.left.left = Node(100)
print("with 100 under 80:", "Yes" if is_balanced(root) else "No")#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
int check(Node* n) { // height of n, or -1 if the subtree is unbalanced
if (!n) return 0;
int lh = check(n->left);
if (lh == -1) return -1; // short-circuit: no need to look at the right side
int rh = check(n->right);
if (rh == -1 || abs(lh - rh) > 1) return -1;
return 1 + max(lh, rh);
}
bool isBalanced(Node* root) { return check(root) != -1; }
int main() {
Node* root = sample();
cout << "sample tree: " << (isBalanced(root) ? "Yes" : "No") << "\n";
root->right->right->left->left = new Node(100);
cout << "with 100 under 80: " << (isBalanced(root) ? "Yes" : "No") << "\n";
}public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static int check(Node n) { // height of n, or -1 if the subtree is unbalanced
if (n == null) return 0;
int lh = check(n.left);
if (lh == -1) return -1; // short-circuit: no need to look at the right side
int rh = check(n.right);
if (rh == -1 || Math.abs(lh - rh) > 1) return -1;
return 1 + Math.max(lh, rh);
}
static boolean isBalanced(Node root) { return check(root) != -1; }
public static void main(String[] args) {
Node root = sample();
System.out.println("sample tree: " + (isBalanced(root) ? "Yes" : "No"));
root.right.right.left.left = new Node(100);
System.out.println("with 100 under 80: " + (isBalanced(root) ? "Yes" : "No"));
}
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function check(n) { // height of n, or -1 if the subtree is unbalanced
if (!n) return 0;
const lh = check(n.left);
if (lh === -1) return -1; // short-circuit: no need to look at the right side
const rh = check(n.right);
if (rh === -1 || Math.abs(lh - rh) > 1) return -1;
return 1 + Math.max(lh, rh);
}
const isBalanced = root => check(root) !== -1;
const root = sample();
console.log("sample tree:", isBalanced(root) ? "Yes" : "No");
root.right.right.left.left = new Node(100);
console.log("with 100 under 80:", isBalanced(root) ? "Yes" : "No");sample tree: Yes
with 100 under 80: NoTime O(n) · Space O(h)
Vertical traversal
hd: -2 -1 0 1 2 3
10
20 30
40 50 60 70
80 90
column -2: 40 column 1: 30 80
column -1: 20 column 2: 70
column 0: 10 50 60 column 3: 90from collections import deque
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def vertical(root):
if root is None:
return
groups = {} # hd → keys in level order
q = deque([(root, 0)]) # node travels with its hd
while q:
node, hd = q.popleft()
groups.setdefault(hd, []).append(node.key)
if node.left:
q.append((node.left, hd - 1))
if node.right:
q.append((node.right, hd + 1))
for hd in sorted(groups): # leftmost column first
print(*groups[hd])
vertical(sample())#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
void vertical(Node* root) {
if (!root) return;
map<int, vector<int>> groups; // std::map is ordered: leftmost column first
queue<pair<Node*, int>> q; // node travels with its hd
q.push({root, 0});
while (!q.empty()) {
auto [node, hd] = q.front(); q.pop();
groups[hd].push_back(node->key);
if (node->left) q.push({node->left, hd - 1});
if (node->right) q.push({node->right, hd + 1});
}
for (auto& column : groups) {
const vector<int>& keys = column.second;
for (size_t i = 0; i < keys.size(); i++) cout << (i ? " " : "") << keys[i];
cout << "\n";
}
}
int main() { vertical(sample()); }import java.util.*;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static void vertical(Node root) {
if (root == null) return;
TreeMap<Integer, List<Integer>> groups = new TreeMap<>(); // sorted by hd
Queue<Node> q = new ArrayDeque<>();
Queue<Integer> hds = new ArrayDeque<>(); // hd travels next to its node
q.add(root); hds.add(0);
while (!q.isEmpty()) {
Node node = q.poll();
int hd = hds.poll();
groups.computeIfAbsent(hd, k -> new ArrayList<>()).add(node.key);
if (node.left != null) { q.add(node.left); hds.add(hd - 1); }
if (node.right != null) { q.add(node.right); hds.add(hd + 1); }
}
for (List<Integer> keys : groups.values()) { // leftmost column first
StringBuilder sb = new StringBuilder();
for (int k : keys) sb.append(k).append(' ');
System.out.println(sb.toString().trim());
}
}
public static void main(String[] args) { vertical(sample()); }
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function vertical(root) {
if (!root) return;
const groups = new Map(); // hd → keys in level order
const q = [[root, 0]]; // node travels with its hd
while (q.length) {
const [node, hd] = q.shift();
if (!groups.has(hd)) groups.set(hd, []);
groups.get(hd).push(node.key);
if (node.left) q.push([node.left, hd - 1]);
if (node.right) q.push([node.right, hd + 1]);
}
const hds = [...groups.keys()].sort((a, b) => a - b); // leftmost column first
for (const hd of hds) console.log(groups.get(hd).join(" "));
}
vertical(sample());40
20
10 50 60
30 80
70
90Time O(n log n) — sorting / ordered map over the columns · Space O(n)
Bottom view of a binary tree
from collections import deque
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def views(root):
bottom, top = {}, {}
q = deque([(root, 0)])
while q:
node, hd = q.popleft()
bottom[hd] = node.key # a later node in BFS order overwrites
if hd not in top:
top[hd] = node.key # the first node seen in a column stays
if node.left:
q.append((node.left, hd - 1))
if node.right:
q.append((node.right, hd + 1))
print("bottom:", *(bottom[hd] for hd in sorted(bottom)))
print("top:", *(top[hd] for hd in sorted(top)))
views(sample())#include <iostream>
#include <map>
#include <queue>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
void views(Node* root) {
map<int, int> bottom, top; // ordered by hd
queue<pair<Node*, int>> q;
q.push({root, 0});
while (!q.empty()) {
auto [node, hd] = q.front(); q.pop();
bottom[hd] = node->key; // a later node in BFS order overwrites
if (!top.count(hd)) top[hd] = node->key; // the first node seen in a column stays
if (node->left) q.push({node->left, hd - 1});
if (node->right) q.push({node->right, hd + 1});
}
cout << "bottom:";
for (auto& e : bottom) cout << " " << e.second;
cout << "\ntop:";
for (auto& e : top) cout << " " << e.second;
cout << "\n";
}
int main() { views(sample()); }import java.util.*;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static void views(Node root) {
TreeMap<Integer, Integer> bottom = new TreeMap<>(), top = new TreeMap<>();
Queue<Node> q = new ArrayDeque<>();
Queue<Integer> hds = new ArrayDeque<>();
q.add(root); hds.add(0);
while (!q.isEmpty()) {
Node node = q.poll();
int hd = hds.poll();
bottom.put(hd, node.key); // a later node in BFS order overwrites
top.putIfAbsent(hd, node.key); // the first node seen in a column stays
if (node.left != null) { q.add(node.left); hds.add(hd - 1); }
if (node.right != null) { q.add(node.right); hds.add(hd + 1); }
}
StringBuilder b = new StringBuilder("bottom:"), t = new StringBuilder("top:");
for (int k : bottom.values()) b.append(' ').append(k);
for (int k : top.values()) t.append(' ').append(k);
System.out.println(b);
System.out.println(t);
}
public static void main(String[] args) { views(sample()); }
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function views(root) {
const bottom = new Map(), top = new Map();
const q = [[root, 0]];
while (q.length) {
const [node, hd] = q.shift();
bottom.set(hd, node.key); // a later node in BFS order overwrites
if (!top.has(hd)) top.set(hd, node.key); // the first node seen in a column stays
if (node.left) q.push([node.left, hd - 1]);
if (node.right) q.push([node.right, hd + 1]);
}
const sorted = m => [...m.keys()].sort((a, b) => a - b).map(hd => m.get(hd));
console.log("bottom:", sorted(bottom).join(" "));
console.log("top:", sorted(top).join(" "));
}
views(sample());bottom: 40 20 60 80 70 90
top: 40 20 10 30 70 90Time O(n log n) · Space O(n)
Maximum width of a binary tree
from collections import deque
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def max_width(root):
if root is None:
return 0
q = deque([root])
best = 0
while q:
count = len(q) # size of the current level
best = max(best, count)
for _ in range(count):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return best
print("max width:", max_width(sample()))#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
int maxWidth(Node* root) {
if (!root) return 0;
queue<Node*> q;
q.push(root);
int best = 0;
while (!q.empty()) {
int count = q.size(); // size of the current level
best = max(best, count);
for (int i = 0; i < count; i++) {
Node* node = q.front(); q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return best;
}
int main() { cout << "max width: " << maxWidth(sample()) << "\n"; }import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static int maxWidth(Node root) {
if (root == null) return 0;
Queue<Node> q = new ArrayDeque<>();
q.add(root);
int best = 0;
while (!q.isEmpty()) {
int count = q.size(); // size of the current level
best = Math.max(best, count);
for (int i = 0; i < count; i++) {
Node node = q.poll();
if (node.left != null) q.add(node.left);
if (node.right != null) q.add(node.right);
}
}
return best;
}
public static void main(String[] args) { System.out.println("max width: " + maxWidth(sample())); }
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function maxWidth(root) {
if (!root) return 0;
const q = [root];
let best = 0;
while (q.length) {
const count = q.length; // size of the current level
best = Math.max(best, count);
for (let i = 0; i < count; i++) {
const node = q.shift();
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
}
return best;
}
console.log("max width:", maxWidth(sample()));max width: 4Time O(n) · Space O(w)
Convert a binary tree to a doubly linked list
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
prev = None # node visited just before the current one
def to_dll(node): # returns the head of the list
global prev
if node is None:
return None
head = to_dll(node.left) # inorder: left subtree first
if prev is None:
head = node # first node visited → head
else:
prev.right = node # link prev <-> node
node.left = prev
prev = node
to_dll(node.right)
return head
head = to_dll(sample())
keys, tail = [], None
n = head
while n:
keys.append(str(n.key)); tail = n; n = n.right
print("forward:", " <-> ".join(keys))
print("backward:", end=" ")
while tail:
print(tail.key, end=" "); tail = tail.left
print()#include <iostream>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
Node* last = nullptr; // node visited just before the current one (`prev` would clash with std::prev)
Node* toDLL(Node* node) { // returns the head of the list
if (!node) return nullptr;
Node* head = toDLL(node->left); // inorder: left subtree first
if (!last) {
head = node; // first node visited → head
} else {
last->right = node; // link last <-> node
node->left = last;
}
last = node;
toDLL(node->right);
return head;
}
int main() {
Node* head = toDLL(sample());
Node* tail = nullptr;
cout << "forward: ";
for (Node* n = head; n; n = n->right) {
cout << (n == head ? "" : " <-> ") << n->key;
tail = n;
}
cout << "\nbackward: ";
for (Node* n = tail; n; n = n->left) cout << n->key << " ";
cout << "\n";
}public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static Node prev = null; // node visited just before the current one
static Node toDLL(Node node) { // returns the head of the list
if (node == null) return null;
Node head = toDLL(node.left); // inorder: left subtree first
if (prev == null) {
head = node; // first node visited → head
} else {
prev.right = node; // link prev <-> node
node.left = prev;
}
prev = node;
toDLL(node.right);
return head;
}
public static void main(String[] args) {
Node head = toDLL(sample());
Node tail = null;
StringBuilder sb = new StringBuilder("forward: ");
for (Node n = head; n != null; n = n.right) {
sb.append(n == head ? "" : " <-> ").append(n.key);
tail = n;
}
System.out.println(sb);
sb = new StringBuilder("backward:");
for (Node n = tail; n != null; n = n.left) sb.append(' ').append(n.key);
System.out.println(sb);
}
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
let prev = null; // node visited just before the current one
function toDLL(node) { // returns the head of the list
if (!node) return null;
let head = toDLL(node.left); // inorder: left subtree first
if (!prev) {
head = node; // first node visited → head
} else {
prev.right = node; // link prev <-> node
node.left = prev;
}
prev = node;
toDLL(node.right);
return head;
}
const head = toDLL(sample());
const keys = [];
let tail = null;
for (let n = head; n; n = n.right) { keys.push(n.key); tail = n; }
console.log("forward:", keys.join(" <-> "));
const back = [];
for (let n = tail; n; n = n.left) back.push(n.key);
console.log("backward:", back.join(" "));forward: 40 <-> 20 <-> 50 <-> 10 <-> 60 <-> 30 <-> 80 <-> 70 <-> 90
backward: 90 70 80 30 60 10 50 20 40Time O(n) · Space O(h) recursion — no extra nodes
Construct a binary tree from inorder and preorder
pre = 10 | 20 40 50 | 30 60 70 80 90 root = pre[0] = 10
in = 40 20 50 | 10 | 60 30 80 70 90 left of 10 in inorder → left subtree
^^^^^^^^ ^^^^^^^^^^^^^^ right of 10 → right subtree
left (3 keys) right (5 keys)The straightforward version searches the inorder slice linearly for the root — O(n) per node, O(n²) in total on a skewed tree:
from collections import deque
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
pre_index = 0 # next preorder key to use
def build(pre, ino, lo, hi): # builds the subtree whose inorder is ino[lo..hi]
global pre_index
if lo > hi:
return None
root = Node(pre[pre_index])
pre_index += 1
mid = ino.index(root.key, lo, hi + 1) # linear search → O(n) per node
root.left = build(pre, ino, lo, mid - 1) # left first: it consumes the next preorder keys
root.right = build(pre, ino, mid + 1, hi)
return root
def print_levels(root):
q = deque([root])
while q:
print(*(n.key for n in q))
q = deque(c for n in q for c in (n.left, n.right) if c)
pre = [10, 20, 40, 50, 30, 60, 70, 80, 90]
ino = [40, 20, 50, 10, 60, 30, 80, 70, 90]
print_levels(build(pre, ino, 0, len(ino) - 1))10
20 30
40 50 60 70
80 90from collections import deque
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def build_tree(pre, ino):
pos = {key: i for i, key in enumerate(ino)} # key → index in inorder
state = {"next": 0} # next preorder key to use
def build(lo, hi): # subtree whose inorder is ino[lo..hi]
if lo > hi:
return None
root = Node(pre[state["next"]])
state["next"] += 1
mid = pos[root.key] # O(1) split point
root.left = build(lo, mid - 1) # left first (preorder order)
root.right = build(mid + 1, hi)
return root
return build(0, len(ino) - 1)
def print_levels(root):
q = deque([root])
while q:
print(*(n.key for n in q))
q = deque(c for n in q for c in (n.left, n.right) if c)
pre = [10, 20, 40, 50, 30, 60, 70, 80, 90]
ino = [40, 20, 50, 10, 60, 30, 80, 70, 90]
print_levels(build_tree(pre, ino))#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
unordered_map<int, int> pos; // key → index in inorder
int nextPre = 0; // next preorder key to use
Node* build(const vector<int>& pre, int lo, int hi) { // subtree whose inorder is in[lo..hi]
if (lo > hi) return nullptr;
Node* root = new Node(pre[nextPre++]);
int mid = pos[root->key]; // O(1) split point
root->left = build(pre, lo, mid - 1); // left first (preorder order)
root->right = build(pre, mid + 1, hi);
return root;
}
void printLevels(Node* root) {
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int count = q.size();
for (int i = 0; i < count; i++) {
Node* n = q.front(); q.pop();
cout << (i ? " " : "") << n->key;
if (n->left) q.push(n->left);
if (n->right) q.push(n->right);
}
cout << "\n";
}
}
int main() {
vector<int> pre = {10, 20, 40, 50, 30, 60, 70, 80, 90};
vector<int> in = {40, 20, 50, 10, 60, 30, 80, 70, 90};
int n = in.size();
for (int i = 0; i < n; i++) pos[in[i]] = i;
printLevels(build(pre, 0, n - 1));
}import java.util.*;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
}
static Map<Integer, Integer> pos = new HashMap<>(); // key → index in inorder
static int nextPre = 0; // next preorder key to use
static Node build(int[] pre, int lo, int hi) { // subtree whose inorder is in[lo..hi]
if (lo > hi) return null;
Node root = new Node(pre[nextPre++]);
int mid = pos.get(root.key); // O(1) split point
root.left = build(pre, lo, mid - 1); // left first (preorder order)
root.right = build(pre, mid + 1, hi);
return root;
}
static void printLevels(Node root) {
Queue<Node> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
int count = q.size();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < count; i++) {
Node n = q.poll();
sb.append(i > 0 ? " " : "").append(n.key);
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
System.out.println(sb);
}
}
public static void main(String[] args) {
int[] pre = {10, 20, 40, 50, 30, 60, 70, 80, 90};
int[] in = {40, 20, 50, 10, 60, 30, 80, 70, 90};
for (int i = 0; i < in.length; i++) pos.put(in[i], i);
printLevels(build(pre, 0, in.length - 1));
}
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
function buildTree(pre, ino) {
const pos = new Map(ino.map((key, i) => [key, i])); // key → index in inorder
let nextPre = 0; // next preorder key to use
function build(lo, hi) { // subtree whose inorder is ino[lo..hi]
if (lo > hi) return null;
const root = new Node(pre[nextPre++]);
const mid = pos.get(root.key); // O(1) split point
root.left = build(lo, mid - 1); // left first (preorder order)
root.right = build(mid + 1, hi);
return root;
}
return build(0, ino.length - 1);
}
function printLevels(root) {
let level = [root];
while (level.length) {
console.log(level.map(n => n.key).join(" "));
level = level.flatMap(n => [n.left, n.right].filter(Boolean));
}
}
const pre = [10, 20, 40, 50, 30, 60, 70, 80, 90];
const ino = [40, 20, 50, 10, 60, 30, 80, 70, 90];
printLevels(buildTree(pre, ino));10
20 30
40 50 60 70
80 90Time O(n) · Space O(n) for the map + O(h) recursion
Spiral (zigzag) level order traversal
Even levels (0, 2, …) are printed left to right, odd levels right to left — so level 1 of the sample prints 30 20 and level 3 prints 90 80.
from collections import deque
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def spiral(root):
if root is None:
return
q = deque([root])
stack = []
reverse = False # level 0 is left to right
while q:
for _ in range(len(q)):
node = q.popleft()
if reverse:
stack.append(node.key) # hold back, print reversed later
else:
print(node.key, end=" ")
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
while stack: # empty only on reversed levels
print(stack.pop(), end=" ")
reverse = not reverse
print()
spiral(sample())#include <iostream>
#include <queue>
#include <stack>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
void spiral(Node* root) {
if (!root) return;
queue<Node*> q;
stack<int> st;
bool reverse = false; // level 0 is left to right
q.push(root);
while (!q.empty()) {
int count = q.size();
for (int i = 0; i < count; i++) {
Node* node = q.front(); q.pop();
if (reverse) st.push(node->key); // hold back, print reversed later
else cout << node->key << " ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
while (!st.empty()) { // empty only on reversed levels
cout << st.top() << " ";
st.pop();
}
reverse = !reverse;
}
cout << "\n";
}
int main() { spiral(sample()); }import java.util.*;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static void spiral(Node root) {
if (root == null) return;
Queue<Node> q = new ArrayDeque<>();
Deque<Integer> stack = new ArrayDeque<>();
boolean reverse = false; // level 0 is left to right
q.add(root);
StringBuilder sb = new StringBuilder();
while (!q.isEmpty()) {
int count = q.size();
for (int i = 0; i < count; i++) {
Node node = q.poll();
if (reverse) stack.push(node.key); // hold back, print reversed later
else sb.append(node.key).append(' ');
if (node.left != null) q.add(node.left);
if (node.right != null) q.add(node.right);
}
while (!stack.isEmpty()) sb.append(stack.pop()).append(' '); // reversed levels only
reverse = !reverse;
}
System.out.println(sb.toString().trim());
}
public static void main(String[] args) { spiral(sample()); }
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function spiral(root) {
if (!root) return;
const q = [root], stack = [], out = [];
let reverse = false; // level 0 is left to right
while (q.length) {
const count = q.length;
for (let i = 0; i < count; i++) {
const node = q.shift();
if (reverse) stack.push(node.key); // hold back, print reversed later
else out.push(node.key);
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
while (stack.length) out.push(stack.pop()); // reversed levels only
reverse = !reverse;
}
console.log(out.join(" "));
}
spiral(sample());10 30 20 40 50 60 70 90 80Time O(n) · Space O(w)
Start
Push the root onto
s1.While either stack is non-empty
Drain
s1(prints left → right): for each popped node pushleft, thenrightontos2.Then drain
s2(prints right → left): for each popped node push
right, thenleftontos1.
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def spiral(root):
if root is None:
return
s1, s2 = [root], [] # s1: left→right level, s2: right→left level
while s1 or s2:
while s1:
node = s1.pop()
print(node.key, end=" ")
if node.left: # left then right → s2 pops right first
s2.append(node.left)
if node.right:
s2.append(node.right)
while s2:
node = s2.pop()
print(node.key, end=" ")
if node.right: # right then left → s1 pops left first
s1.append(node.right)
if node.left:
s1.append(node.left)
print()
spiral(sample())#include <iostream>
#include <stack>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
void spiral(Node* root) {
if (!root) return;
stack<Node*> s1, s2; // s1: left→right level, s2: right→left level
s1.push(root);
while (!s1.empty() || !s2.empty()) {
while (!s1.empty()) {
Node* node = s1.top(); s1.pop();
cout << node->key << " ";
if (node->left) s2.push(node->left); // left then right → s2 pops right first
if (node->right) s2.push(node->right);
}
while (!s2.empty()) {
Node* node = s2.top(); s2.pop();
cout << node->key << " ";
if (node->right) s1.push(node->right); // right then left → s1 pops left first
if (node->left) s1.push(node->left);
}
}
cout << "\n";
}
int main() { spiral(sample()); }import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static void spiral(Node root) {
if (root == null) return;
Deque<Node> s1 = new ArrayDeque<>(), s2 = new ArrayDeque<>(); // s1: left→right, s2: right→left
s1.push(root);
StringBuilder sb = new StringBuilder();
while (!s1.isEmpty() || !s2.isEmpty()) {
while (!s1.isEmpty()) {
Node node = s1.pop();
sb.append(node.key).append(' ');
if (node.left != null) s2.push(node.left); // left then right → s2 pops right first
if (node.right != null) s2.push(node.right);
}
while (!s2.isEmpty()) {
Node node = s2.pop();
sb.append(node.key).append(' ');
if (node.right != null) s1.push(node.right); // right then left → s1 pops left first
if (node.left != null) s1.push(node.left);
}
}
System.out.println(sb.toString().trim());
}
public static void main(String[] args) { spiral(sample()); }
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function spiral(root) {
if (!root) return;
const s1 = [root], s2 = [], out = []; // s1: left→right level, s2: right→left level
while (s1.length || s2.length) {
while (s1.length) {
const node = s1.pop();
out.push(node.key);
if (node.left) s2.push(node.left); // left then right → s2 pops right first
if (node.right) s2.push(node.right);
}
while (s2.length) {
const node = s2.pop();
out.push(node.key);
if (node.right) s1.push(node.right); // right then left → s1 pops left first
if (node.left) s1.push(node.left);
}
}
console.log(out.join(" "));
}
spiral(sample());10 30 20 40 50 60 70 90 80Time O(n) · Space O(w)
Diameter of a binary tree
10
/ \
20 30
/ \ / \
40 50 60 70
/ \
80 90
longest path: 40 – 20 – 10 – 30 – 70 – 80 (6 nodes, through the root)
another: 80 – 70 – 90 (3 nodes, not through the root)class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def height(n):
return 0 if n is None else 1 + max(height(n.left), height(n.right))
def diameter(n):
if n is None:
return 0
through = 1 + height(n.left) + height(n.right) # longest path through n — O(n) each time
return max(through, diameter(n.left), diameter(n.right))
print("diameter:", diameter(sample()))diameter: 6class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
best = 0 # the diameter, recorded on the side
def height(n): # returns height, updates best
global best
if n is None:
return 0
lh = height(n.left)
rh = height(n.right)
best = max(best, 1 + lh + rh) # longest path through n
return 1 + max(lh, rh)
height(sample())
print("diameter:", best)#include <iostream>
#include <algorithm>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
int best = 0; // the diameter, recorded on the side
int height(Node* n) { // returns height, updates best
if (!n) return 0;
int lh = height(n->left);
int rh = height(n->right);
best = max(best, 1 + lh + rh); // longest path through n
return 1 + max(lh, rh);
}
int main() {
height(sample());
cout << "diameter: " << best << "\n";
}public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static int best = 0; // the diameter, recorded on the side
static int height(Node n) { // returns height, updates best
if (n == null) return 0;
int lh = height(n.left);
int rh = height(n.right);
best = Math.max(best, 1 + lh + rh); // longest path through n
return 1 + Math.max(lh, rh);
}
public static void main(String[] args) {
height(sample());
System.out.println("diameter: " + best);
}
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
let best = 0; // the diameter, recorded on the side
function height(n) { // returns height, updates best
if (!n) return 0;
const lh = height(n.left);
const rh = height(n.right);
best = Math.max(best, 1 + lh + rh); // longest path through n
return 1 + Math.max(lh, rh);
}
height(sample());
console.log("diameter:", best);diameter: 6Time O(n) · Space O(h)
Lowest common ancestor (LCA)
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def find_path(n, key, path): # fills path with root → key; False if absent
if n is None:
return False
path.append(n.key)
if n.key == key or find_path(n.left, key, path) or find_path(n.right, key, path):
return True
path.pop() # key not below n: backtrack
return False
def lca(root, a, b):
pa, pb = [], []
if not find_path(root, a, pa) or not find_path(root, b, pb):
return None # one of the keys is missing
i = 0
while i < len(pa) and i < len(pb) and pa[i] == pb[i]:
i += 1 # walk while the paths agree
return pa[i - 1] # last node they shared
root = sample()
for a, b in [(40, 50), (80, 30), (50, 90), (80, 90)]:
print(f"LCA({a}, {b}) = {lca(root, a, b)}")#include <iostream>
#include <vector>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
bool findPath(Node* n, int key, vector<int>& path) { // fills path with root → key
if (!n) return false;
path.push_back(n->key);
if (n->key == key || findPath(n->left, key, path) || findPath(n->right, key, path))
return true;
path.pop_back(); // key not below n: backtrack
return false;
}
int lca(Node* root, int a, int b) {
vector<int> pa, pb;
if (!findPath(root, a, pa) || !findPath(root, b, pb)) return -1; // a key is missing
size_t i = 0;
while (i < pa.size() && i < pb.size() && pa[i] == pb[i]) i++; // walk while they agree
return pa[i - 1]; // last shared node
}
int main() {
Node* root = sample();
int pairs[4][2] = {{40, 50}, {80, 30}, {50, 90}, {80, 90}};
for (auto& p : pairs)
cout << "LCA(" << p[0] << ", " << p[1] << ") = " << lca(root, p[0], p[1]) << "\n";
}import java.util.ArrayList;
import java.util.List;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static boolean findPath(Node n, int key, List<Integer> path) { // fills path with root → key
if (n == null) return false;
path.add(n.key);
if (n.key == key || findPath(n.left, key, path) || findPath(n.right, key, path))
return true;
path.remove(path.size() - 1); // key not below n: backtrack
return false;
}
static Integer lca(Node root, int a, int b) {
List<Integer> pa = new ArrayList<>(), pb = new ArrayList<>();
if (!findPath(root, a, pa) || !findPath(root, b, pb)) return null; // a key is missing
int i = 0;
while (i < pa.size() && i < pb.size() && pa.get(i).equals(pb.get(i))) i++; // walk while they agree
return pa.get(i - 1); // last shared node
}
public static void main(String[] args) {
Node root = sample();
int[][] pairs = {{40, 50}, {80, 30}, {50, 90}, {80, 90}};
for (int[] p : pairs)
System.out.println("LCA(" + p[0] + ", " + p[1] + ") = " + lca(root, p[0], p[1]));
}
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function findPath(n, key, path) { // fills path with root → key; false if absent
if (!n) return false;
path.push(n.key);
if (n.key === key || findPath(n.left, key, path) || findPath(n.right, key, path)) return true;
path.pop(); // key not below n: backtrack
return false;
}
function lca(root, a, b) {
const pa = [], pb = [];
if (!findPath(root, a, pa) || !findPath(root, b, pb)) return null; // a key is missing
let i = 0;
while (i < pa.length && i < pb.length && pa[i] === pb[i]) i++; // walk while they agree
return pa[i - 1]; // last shared node
}
const root = sample();
for (const [a, b] of [[40, 50], [80, 30], [50, 90], [80, 90]])
console.log(`LCA(${a}, ${b}) = ${lca(root, a, b)}`);LCA(40, 50) = 20
LCA(80, 30) = 30
LCA(50, 90) = 10
LCA(80, 90) = 70Time O(n) · Space O(h) for the two paths
Case at node n | Return |
|---|---|
n is a or b | n (no need to look below: if the other key is beneath, n is still the LCA) |
| left returns a node and right returns a node | n — the keys are on different sides |
| only one side returns a node | that node (both keys are below it, or only one was found) |
| neither side returns a node | None |
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def lca(n, a, b):
if n is None:
return None
if n.key == a or n.key == b:
return n # case 1: found one of the keys
left = lca(n.left, a, b)
right = lca(n.right, a, b)
if left and right:
return n # case 2: one key on each side → n is the LCA
return left if left else right # case 3/4: pass up whatever was found
root = sample()
for a, b in [(40, 50), (80, 30), (50, 90), (80, 90)]:
print(f"LCA({a}, {b}) = {lca(root, a, b).key}")#include <iostream>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
Node* lca(Node* n, int a, int b) {
if (!n) return nullptr;
if (n->key == a || n->key == b) return n; // case 1: found one of the keys
Node* left = lca(n->left, a, b);
Node* right = lca(n->right, a, b);
if (left && right) return n; // case 2: one key on each side → n is the LCA
return left ? left : right; // case 3/4: pass up whatever was found
}
int main() {
Node* root = sample();
int pairs[4][2] = {{40, 50}, {80, 30}, {50, 90}, {80, 90}};
for (auto& p : pairs)
cout << "LCA(" << p[0] << ", " << p[1] << ") = " << lca(root, p[0], p[1])->key << "\n";
}public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static Node lca(Node n, int a, int b) {
if (n == null) return null;
if (n.key == a || n.key == b) return n; // case 1: found one of the keys
Node left = lca(n.left, a, b);
Node right = lca(n.right, a, b);
if (left != null && right != null) return n; // case 2: one key on each side → n is the LCA
return left != null ? left : right; // case 3/4: pass up whatever was found
}
public static void main(String[] args) {
Node root = sample();
int[][] pairs = {{40, 50}, {80, 30}, {50, 90}, {80, 90}};
for (int[] p : pairs)
System.out.println("LCA(" + p[0] + ", " + p[1] + ") = " + lca(root, p[0], p[1]).key);
}
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function lca(n, a, b) {
if (!n) return null;
if (n.key === a || n.key === b) return n; // case 1: found one of the keys
const left = lca(n.left, a, b);
const right = lca(n.right, a, b);
if (left && right) return n; // case 2: one key on each side → n is the LCA
return left ? left : right; // case 3/4: pass up whatever was found
}
const root = sample();
for (const [a, b] of [[40, 50], [80, 30], [50, 90], [80, 90]])
console.log(`LCA(${a}, ${b}) = ${lca(root, a, b).key}`);LCA(40, 50) = 20
LCA(80, 30) = 30
LCA(50, 90) = 10
LCA(80, 90) = 70Time O(n) · Space O(h)
Burn a binary tree from a leaf
fire starts at 50; each second it spreads to every neighbour (parent and children)
t=0: 50 10 ←t=2
t=1: 20 / \
t=2: 10, 40 t=1→ 20 30 ←t=3
t=3: 30 / \ / \
t=4: 60, 70 t=2→ 40 50 60 70 ←t=4
t=5: 80, 90 t=0 t=4 / \
80 90 ←t=5 → answer 5class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
best = 0
def burn(n, leaf, dist): # returns height; dist[0] = distance of leaf below n, or -1
global best
dist[0] = -1
if n is None:
return 0
if n.key == leaf:
dist[0] = 0 # the fire starts here
return 1
ldist, rdist = [-1], [-1]
lh = burn(n.left, leaf, ldist)
rh = burn(n.right, leaf, rdist)
if ldist[0] != -1: # leaf is in the left subtree
dist[0] = ldist[0] + 1
best = max(best, dist[0] + rh) # up to n, then down the right side
elif rdist[0] != -1: # leaf is in the right subtree
dist[0] = rdist[0] + 1
best = max(best, dist[0] + lh)
return 1 + max(lh, rh)
def burn_time(root, leaf):
global best
best = 0
burn(root, leaf, [-1])
return best
root = sample()
print("burn from 50:", burn_time(root, 50))
print("burn from 60:", burn_time(root, 60))#include <iostream>
#include <algorithm>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
int best = 0;
int burn(Node* n, int leaf, int& dist) { // returns height; dist = distance of leaf below n, or -1
dist = -1;
if (!n) return 0;
if (n->key == leaf) { dist = 0; return 1; } // the fire starts here
int ldist, rdist;
int lh = burn(n->left, leaf, ldist);
int rh = burn(n->right, leaf, rdist);
if (ldist != -1) { // leaf is in the left subtree
dist = ldist + 1;
best = max(best, dist + rh); // up to n, then down the right side
} else if (rdist != -1) { // leaf is in the right subtree
dist = rdist + 1;
best = max(best, dist + lh);
}
return 1 + max(lh, rh);
}
int burnTime(Node* root, int leaf) {
best = 0;
int d;
burn(root, leaf, d);
return best;
}
int main() {
Node* root = sample();
cout << "burn from 50: " << burnTime(root, 50) << "\n";
cout << "burn from 60: " << burnTime(root, 60) << "\n";
}public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static int best = 0;
static int burn(Node n, int leaf, int[] dist) { // returns height; dist[0] = distance of leaf below n, or -1
dist[0] = -1;
if (n == null) return 0;
if (n.key == leaf) { dist[0] = 0; return 1; } // the fire starts here
int[] ldist = {-1}, rdist = {-1};
int lh = burn(n.left, leaf, ldist);
int rh = burn(n.right, leaf, rdist);
if (ldist[0] != -1) { // leaf is in the left subtree
dist[0] = ldist[0] + 1;
best = Math.max(best, dist[0] + rh); // up to n, then down the right side
} else if (rdist[0] != -1) { // leaf is in the right subtree
dist[0] = rdist[0] + 1;
best = Math.max(best, dist[0] + lh);
}
return 1 + Math.max(lh, rh);
}
static int burnTime(Node root, int leaf) {
best = 0;
burn(root, leaf, new int[]{-1});
return best;
}
public static void main(String[] args) {
Node root = sample();
System.out.println("burn from 50: " + burnTime(root, 50));
System.out.println("burn from 60: " + burnTime(root, 60));
}
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
let best = 0;
function burn(n, leaf, dist) { // returns height; dist.v = distance of leaf below n, or -1
dist.v = -1;
if (!n) return 0;
if (n.key === leaf) { dist.v = 0; return 1; } // the fire starts here
const ldist = { v: -1 }, rdist = { v: -1 };
const lh = burn(n.left, leaf, ldist);
const rh = burn(n.right, leaf, rdist);
if (ldist.v !== -1) { // leaf is in the left subtree
dist.v = ldist.v + 1;
best = Math.max(best, dist.v + rh); // up to n, then down the right side
} else if (rdist.v !== -1) { // leaf is in the right subtree
dist.v = rdist.v + 1;
best = Math.max(best, dist.v + lh);
}
return 1 + Math.max(lh, rh);
}
function burnTime(root, leaf) {
best = 0;
burn(root, leaf, { v: -1 });
return best;
}
const root = sample();
console.log("burn from 50:", burnTime(root, 50));
console.log("burn from 60:", burnTime(root, 60));burn from 50: 5
burn from 60: 4Time O(n) · Space O(h)
Count nodes in a complete binary tree
10 left height (10 20 40 80) = 4
/ \ right height (10 30 70) = 3 → not perfect, recurse
20 30
/ \ / \ subtree 30: left 2, right 2 → perfect → 2² − 1 = 3 nodes
40 50 60 70 subtree 20: left 3, right 2 → recurse
/ \ / subtree 40: left 2, right 2 → perfect → 3 nodes
80 90 100 subtree 50: left 2, right 1 → recurse → 2 nodes
total = 1 + (1 + 3 + 2) + 3 = 10class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def count_complete(n):
lh = rh = 0
cur = n
while cur: # height along the leftmost path
lh += 1
cur = cur.left
cur = n
while cur: # height along the rightmost path
rh += 1
cur = cur.right
if lh == rh:
return (1 << lh) - 1 # perfect subtree: 2^h - 1 nodes, no visit needed
return 1 + count_complete(n.left) + count_complete(n.right)
complete = Node(10, Node(20, Node(40, Node(80), Node(90)), Node(50, Node(100))),
Node(30, Node(60), Node(70)))
perfect = Node(10, Node(20, Node(40), Node(50)), Node(30, Node(60), Node(70)))
print("complete tree (10 nodes):", count_complete(complete))
print("perfect tree (7 nodes):", count_complete(perfect))#include <iostream>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
int countComplete(Node* n) {
int lh = 0, rh = 0;
for (Node* cur = n; cur; cur = cur->left) lh++; // height along the leftmost path
for (Node* cur = n; cur; cur = cur->right) rh++; // height along the rightmost path
if (lh == rh) return (1 << lh) - 1; // perfect subtree: 2^h - 1 nodes
return 1 + countComplete(n->left) + countComplete(n->right);
}
int main() {
Node* complete = new Node(10, new Node(20, new Node(40, new Node(80), new Node(90)), new Node(50, new Node(100))),
new Node(30, new Node(60), new Node(70)));
Node* perfect = new Node(10, new Node(20, new Node(40), new Node(50)), new Node(30, new Node(60), new Node(70)));
cout << "complete tree (10 nodes): " << countComplete(complete) << "\n";
cout << "perfect tree (7 nodes): " << countComplete(perfect) << "\n";
}public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static int countComplete(Node n) {
int lh = 0, rh = 0;
for (Node cur = n; cur != null; cur = cur.left) lh++; // height along the leftmost path
for (Node cur = n; cur != null; cur = cur.right) rh++; // height along the rightmost path
if (lh == rh) return (1 << lh) - 1; // perfect subtree: 2^h - 1 nodes
return 1 + countComplete(n.left) + countComplete(n.right);
}
public static void main(String[] args) {
Node complete = new Node(10, new Node(20, new Node(40, new Node(80), new Node(90)), new Node(50, new Node(100), null)),
new Node(30, new Node(60), new Node(70)));
Node perfect = new Node(10, new Node(20, new Node(40), new Node(50)), new Node(30, new Node(60), new Node(70)));
System.out.println("complete tree (10 nodes): " + countComplete(complete));
System.out.println("perfect tree (7 nodes): " + countComplete(perfect));
}
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
function countComplete(n) {
let lh = 0, rh = 0;
for (let cur = n; cur; cur = cur.left) lh++; // height along the leftmost path
for (let cur = n; cur; cur = cur.right) rh++; // height along the rightmost path
if (lh === rh) return (1 << lh) - 1; // perfect subtree: 2^h - 1 nodes
return 1 + countComplete(n.left) + countComplete(n.right);
}
const complete = new Node(10, new Node(20, new Node(40, new Node(80), new Node(90)), new Node(50, new Node(100))),
new Node(30, new Node(60), new Node(70)));
const perfect = new Node(10, new Node(20, new Node(40), new Node(50)), new Node(30, new Node(60), new Node(70)));
console.log("complete tree (10 nodes):", countComplete(complete));
console.log("perfect tree (7 nodes):", countComplete(perfect));complete tree (10 nodes): 10
perfect tree (7 nodes): 7Time O(log² n) · Space O(log n)
Serialize and deserialize a binary tree
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def inorder(n, out):
if n:
inorder(n.left, out); out.append(n.key); inorder(n.right, out)
def preorder(n, out):
if n:
out.append(n.key); preorder(n.left, out); preorder(n.right, out)
def serialize(root):
arr = []
inorder(root, arr)
arr.append(-1) # separator
preorder(root, arr)
return arr
def deserialize(arr):
sep = arr.index(-1)
ino, pre = arr[:sep], arr[sep + 1:]
pos = {key: i for i, key in enumerate(ino)}
state = {"next": 0}
def build(lo, hi):
if lo > hi:
return None
root = Node(pre[state["next"]]); state["next"] += 1
mid = pos[root.key]
root.left = build(lo, mid - 1)
root.right = build(mid + 1, hi)
return root
return build(0, len(ino) - 1)
data = serialize(sample())
print("serialized:", *data)
again = serialize(deserialize(data))
print("round trip identical:", "Yes" if again == data else "No")serialized: 40 20 50 10 60 30 80 70 90 -1 10 20 40 50 30 60 70 80 90
round trip identical: Yes 10 preorder with empties:
/ \ 10 20 -1 -1 30 -1 -1
20 30 ^^^^^^^^ ^^^^^^^^
20 has no children, 30 has no childrenclass Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
EMPTY = -1
def serialize(n, out): # preorder, writing EMPTY for every missing child
if n is None:
out.append(EMPTY)
return
out.append(n.key)
serialize(n.left, out)
serialize(n.right, out)
def deserialize(arr, pos): # pos[0] = next value to read, shared by all calls
val = arr[pos[0]]
pos[0] += 1
if val == EMPTY:
return None
n = Node(val)
n.left = deserialize(arr, pos) # the following values describe the left subtree…
n.right = deserialize(arr, pos) # …then the right one
return n
def inorder(n):
if n:
inorder(n.left); print(n.key, end=" "); inorder(n.right)
data = []
serialize(sample(), data)
print("serialized:", *data)
rebuilt = deserialize(data, [0])
print("rebuilt inorder:", end=" "); inorder(rebuilt); print()
again = []
serialize(rebuilt, again)
print("round trip identical:", "Yes" if again == data else "No")#include <iostream>
#include <vector>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
const int EMPTY = -1;
void serialize(Node* n, vector<int>& out) { // preorder, writing EMPTY for every missing child
if (!n) { out.push_back(EMPTY); return; }
out.push_back(n->key);
serialize(n->left, out);
serialize(n->right, out);
}
Node* deserialize(const vector<int>& arr, int& pos) { // pos = next value to read, shared
int val = arr[pos++];
if (val == EMPTY) return nullptr;
Node* n = new Node(val);
n->left = deserialize(arr, pos); // the following values describe the left subtree…
n->right = deserialize(arr, pos); // …then the right one
return n;
}
void inorder(Node* n) {
if (!n) return;
inorder(n->left); cout << n->key << " "; inorder(n->right);
}
int main() {
vector<int> data;
serialize(sample(), data);
cout << "serialized:";
for (int v : data) cout << " " << v;
cout << "\n";
int pos = 0;
Node* rebuilt = deserialize(data, pos);
cout << "rebuilt inorder: "; inorder(rebuilt); cout << "\n";
vector<int> again;
serialize(rebuilt, again);
cout << "round trip identical: " << (again == data ? "Yes" : "No") << "\n";
}import java.util.ArrayList;
import java.util.List;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static final int EMPTY = -1;
static int pos = 0; // next value to read, shared by all calls
static void serialize(Node n, List<Integer> out) { // preorder, writing EMPTY for every missing child
if (n == null) { out.add(EMPTY); return; }
out.add(n.key);
serialize(n.left, out);
serialize(n.right, out);
}
static Node deserialize(List<Integer> arr) {
int val = arr.get(pos++);
if (val == EMPTY) return null;
Node n = new Node(val);
n.left = deserialize(arr); // the following values describe the left subtree…
n.right = deserialize(arr); // …then the right one
return n;
}
static void inorder(Node n, StringBuilder sb) {
if (n == null) return;
inorder(n.left, sb); sb.append(n.key).append(' '); inorder(n.right, sb);
}
public static void main(String[] args) {
List<Integer> data = new ArrayList<>();
serialize(sample(), data);
StringBuilder sb = new StringBuilder("serialized:");
for (int v : data) sb.append(' ').append(v);
System.out.println(sb);
pos = 0;
Node rebuilt = deserialize(data);
sb = new StringBuilder("rebuilt inorder: ");
inorder(rebuilt, sb);
System.out.println(sb.toString().trim());
List<Integer> again = new ArrayList<>();
serialize(rebuilt, again);
System.out.println("round trip identical: " + (again.equals(data) ? "Yes" : "No"));
}
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
const EMPTY = -1;
function serialize(n, out) { // preorder, writing EMPTY for every missing child
if (!n) { out.push(EMPTY); return; }
out.push(n.key);
serialize(n.left, out);
serialize(n.right, out);
}
let pos = 0; // next value to read, shared by all calls
function deserialize(arr) {
const val = arr[pos++];
if (val === EMPTY) return null;
const n = new Node(val);
n.left = deserialize(arr); // the following values describe the left subtree…
n.right = deserialize(arr); // …then the right one
return n;
}
const inorder = (n, out) => { if (n) { inorder(n.left, out); out.push(n.key); inorder(n.right, out); } };
const data = [];
serialize(sample(), data);
console.log("serialized:", data.join(" "));
pos = 0;
const rebuilt = deserialize(data);
const keys = [];
inorder(rebuilt, keys);
console.log("rebuilt inorder:", keys.join(" "));
const again = [];
serialize(rebuilt, again);
console.log("round trip identical:", again.join() === data.join() ? "Yes" : "No");serialized: 10 20 40 -1 -1 50 -1 -1 30 60 -1 -1 70 80 -1 -1 90 -1 -1
rebuilt inorder: 40 20 50 10 60 30 80 70 90
round trip identical: YesTime O(n) · Space O(n) — 2n + 1 values
Iterative inorder traversal
Go left
While
curris not empty: pushcurr,curr = curr.left.Visit
Pop the stack into
currand print it — everything to its left has been printed.Go right
curr = curr.right, then repeat from step 1. Finished when the stack is empty andcurris empty.
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def inorder(root):
stack, curr = [], root
while stack or curr:
while curr: # push the whole left spine
stack.append(curr)
curr = curr.left
curr = stack.pop() # leftmost pending node
print(curr.key, end=" ")
curr = curr.right # now its right subtree, same procedure
print()
inorder(sample())#include <iostream>
#include <stack>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
void inorder(Node* root) {
stack<Node*> st;
Node* curr = root;
while (!st.empty() || curr) {
while (curr) { // push the whole left spine
st.push(curr);
curr = curr->left;
}
curr = st.top(); st.pop(); // leftmost pending node
cout << curr->key << " ";
curr = curr->right; // now its right subtree, same procedure
}
cout << "\n";
}
int main() { inorder(sample()); }import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static void inorder(Node root) {
Deque<Node> st = new ArrayDeque<>();
Node curr = root;
StringBuilder sb = new StringBuilder();
while (!st.isEmpty() || curr != null) {
while (curr != null) { // push the whole left spine
st.push(curr);
curr = curr.left;
}
curr = st.pop(); // leftmost pending node
sb.append(curr.key).append(' ');
curr = curr.right; // now its right subtree, same procedure
}
System.out.println(sb.toString().trim());
}
public static void main(String[] args) { inorder(sample()); }
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function inorder(root) {
const st = [], out = [];
let curr = root;
while (st.length || curr) {
while (curr) { // push the whole left spine
st.push(curr);
curr = curr.left;
}
curr = st.pop(); // leftmost pending node
out.push(curr.key);
curr = curr.right; // now its right subtree, same procedure
}
console.log(out.join(" "));
}
inorder(sample());40 20 50 10 60 30 80 70 90Time O(n) · Space O(h) stack
Iterative preorder traversal
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def preorder(root):
if root is None:
return
stack = [root]
while stack:
curr = stack.pop()
print(curr.key, end=" ") # visit on pop
if curr.right:
stack.append(curr.right) # right first …
if curr.left:
stack.append(curr.left) # … so that left is popped next
print()
preorder(sample())#include <iostream>
#include <stack>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
void preorder(Node* root) {
if (!root) return;
stack<Node*> st;
st.push(root);
while (!st.empty()) {
Node* curr = st.top(); st.pop();
cout << curr->key << " "; // visit on pop
if (curr->right) st.push(curr->right); // right first …
if (curr->left) st.push(curr->left); // … so that left is popped next
}
cout << "\n";
}
int main() { preorder(sample()); }import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static void preorder(Node root) {
if (root == null) return;
Deque<Node> st = new ArrayDeque<>();
st.push(root);
StringBuilder sb = new StringBuilder();
while (!st.isEmpty()) {
Node curr = st.pop();
sb.append(curr.key).append(' '); // visit on pop
if (curr.right != null) st.push(curr.right); // right first …
if (curr.left != null) st.push(curr.left); // … so that left is popped next
}
System.out.println(sb.toString().trim());
}
public static void main(String[] args) { preorder(sample()); }
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function preorder(root) {
if (!root) return;
const st = [root], out = [];
while (st.length) {
const curr = st.pop();
out.push(curr.key); // visit on pop
if (curr.right) st.push(curr.right); // right first …
if (curr.left) st.push(curr.left); // … so that left is popped next
}
console.log(out.join(" "));
}
preorder(sample());10 20 40 50 30 60 70 80 90Time O(n) · Space O(n) worst case — the stack can hold up to half the nodes
class Node:
def __init__(self, key, left=None, right=None):
self.key, self.left, self.right = key, left, right
def sample():
return Node(10, Node(20, Node(40), Node(50)),
Node(30, Node(60), Node(70, Node(80), Node(90))))
def preorder(root):
stack, curr = [], root
while stack or curr:
while curr:
print(curr.key, end=" ") # visit on the way down
if curr.right:
stack.append(curr.right) # remember the right child for later
curr = curr.left # keep walking the left spine
if stack:
curr = stack.pop() # resume at the most recent right child
print()
preorder(sample())#include <iostream>
#include <stack>
using namespace std;
struct Node {
int key; Node *left, *right;
Node(int k, Node* l = nullptr, Node* r = nullptr) : key(k), left(l), right(r) {}
};
Node* sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
void preorder(Node* root) {
stack<Node*> st;
Node* curr = root;
while (!st.empty() || curr) {
while (curr) {
cout << curr->key << " "; // visit on the way down
if (curr->right) st.push(curr->right); // remember the right child for later
curr = curr->left; // keep walking the left spine
}
if (!st.empty()) {
curr = st.top(); st.pop(); // resume at the most recent right child
}
}
cout << "\n";
}
int main() { preorder(sample()); }import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
Node(int k, Node l, Node r) { key = k; left = l; right = r; }
}
static Node sample() {
return new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
}
static void preorder(Node root) {
Deque<Node> st = new ArrayDeque<>();
Node curr = root;
StringBuilder sb = new StringBuilder();
while (!st.isEmpty() || curr != null) {
while (curr != null) {
sb.append(curr.key).append(' '); // visit on the way down
if (curr.right != null) st.push(curr.right); // remember the right child for later
curr = curr.left; // keep walking the left spine
}
if (!st.isEmpty()) curr = st.pop(); // resume at the most recent right child
}
System.out.println(sb.toString().trim());
}
public static void main(String[] args) { preorder(sample()); }
}class Node {
constructor(key, left = null, right = null) { this.key = key; this.left = left; this.right = right; }
}
const sample = () =>
new Node(10, new Node(20, new Node(40), new Node(50)),
new Node(30, new Node(60), new Node(70, new Node(80), new Node(90))));
function preorder(root) {
const st = [], out = [];
let curr = root;
while (st.length || curr) {
while (curr) {
out.push(curr.key); // visit on the way down
if (curr.right) st.push(curr.right); // remember the right child for later
curr = curr.left; // keep walking the left spine
}
if (st.length) curr = st.pop(); // resume at the most recent right child
}
console.log(out.join(" "));
}
preorder(sample());10 20 40 50 30 60 70 80 90Time O(n) · Space O(h) stack
| Traversal | Iterative trick | Stack holds |
|---|---|---|
| Inorder | push the left spine, pop–print, go right | O(h) |
| Preorder v1 | pop–print, push right then left | up to O(n) |
| Preorder v2 | print on the way down the left spine, push right children only | O(h) |
| Postorder | preorder with children swapped (root, right, left), then reverse the output — or two stacks | O(n) |
| Level order | a queue instead of a stack | O(w) |
Interview Q&A
Height, depth, level, diameter — what is the difference, and does it count nodes or edges?
Why does the 'return height, record the answer on the side' pattern keep showing up?
Which traversals uniquely determine a binary tree?
How do the bottom view, top view and vertical traversal differ in code?
When would you choose the two-paths LCA over the single-traversal one?
Why is counting a complete binary tree O(log² n) and not O(n)?