Binary trees — across Python, Go, TypeScript & C++

A binary tree node stores a value plus left/right child links. DFS uses O(h) extra space, BFS uses O(w), and every traversal below visits each node once: O(n).

Node definitions

Python	Go	TypeScript	C++
`class Node: def __init__(self, val, left=None, right=None): self.val = val self.left = left; self.right = right`	`type Node struct { Val int Left, Right *Node }`	`type TreeNode = { val: number left: TreeNode \| null right: TreeNode \| null }`	`struct Node { int val; Node* left = nullptr; Node* right = nullptr; };`

DFS — recursive

operation	Python	Go	TypeScript	C++
preorder root, left, right O(n)	`def preorder(root): ans = [] def dfs(n): if n is None: return ans.append(n.val); dfs(n.left); dfs(n.right) dfs(root); return ans`	`visit(n.Val); dfs(n.Left); dfs(n.Right)`	`visit(n.val); dfs(n.left); dfs(n.right)`	`visit(n->val); dfs(n->left); dfs(n->right)`
inorder left, root, right O(n)	`def inorder(root): ans = [] def dfs(n): if n is None: return dfs(n.left); ans.append(n.val); dfs(n.right) dfs(root); return ans`	`func inorder(n *Node) { if n == nil { return } inorder(n.Left) visit(n.Val) inorder(n.Right) }`	`function inorder(n: TreeNode \| null): void { if (!n) return; inorder(n.left); visit(n.val); inorder(n.right); }`	`void inorder(Node* n) { if (!n) return; inorder(n->left); visit(n->val); inorder(n->right); }`
postorder left, right, root O(n)	`def postorder(root): ans = [] def dfs(n): if n is None: return dfs(n.left); dfs(n.right); ans.append(n.val) dfs(root); return ans`	`dfs(n.Left); dfs(n.Right); visit(n.Val)`	`dfs(n.left); dfs(n.right); visit(n.val)`	`dfs(n->left); dfs(n->right); visit(n->val)`

DFS — iterative with stack

operation	Python	Go	TypeScript	C++
preorder O(n)	`def preorder_iter(root): if root is None: return [] ans, st = [], [root] while st: n = st.pop(); ans.append(n.val) if n.right: st.append(n.right) if n.left: st.append(n.left) return ans`	`[]*Node stack; push right then left`	`TreeNode[] stack; push right then left`	`vector<Node*> stack; push right then left`
inorder O(n)	`def inorder_iter(root): ans, st, cur = [], [], root while cur or st: while cur: st.append(cur); cur = cur.left cur = st.pop(); ans.append(cur.val) cur = cur.right return ans`	`walk left; pop; visit; go right`	`walk left; pop; visit; go right`	`walk left; pop; visit; go right`
postorder O(n)	`def postorder_iter(root): if root is None: return [] ans, st = [], [(root, False)] while st: n, seen = st.pop() if seen: ans.append(n.val); continue st.append((n, True)) if n.right: st.append((n.right, False)) if n.left: st.append((n.left, False)) return ans`	`stack of (node, seen); visit when seen`	`stack of [node, seen]; visit when seen`	`stack<pair<Node*, bool>>; visit when seen`

BFS — level order

operation	Python	Go	TypeScript	C++
queue length snapshot O(n)	`from collections import deque def level_order(root): if root is None: return [] ans, q = [], deque([root]) while q: level = [] for _ in range(len(q)): n = q.popleft(); level.append(n.val) if n.left: q.append(n.left) if n.right: q.append(n.right) ans.append(level) return ans`	`for len(q) > 0 { size := len(q) for i := 0; i < size; i++ { n := q[0]; q = q[1:] visit(n.Val) if n.Left != nil { q = append(q, n.Left) } if n.Right != nil { q = append(q, n.Right) } } }`	`let head = 0; while (head < q.length) { const end = q.length; for (; head < end; head++) { const n = q[head]; visit(n.val); if (n.left) q.push(n.left); if (n.right) q.push(n.right); } }`	`while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; i++) { Node* n = q.front(); q.pop(); visit(n->val); if (n->left) q.push(n->left); if (n->right) q.push(n->right); } }`

DFS with return value

operation	Python	Go	TypeScript	C++
answer at node = f(children) O(n)	`def height(root): if root is None: return 0 left = height(root.left) right = height(root.right) return 1 + max(left, right)`	`func height(n *Node) int { if n == nil { return 0 } return 1 + max(height(n.Left), height(n.Right)) }`	`function height(n: TreeNode \| null): number { if (!n) return 0; return 1 + Math.max(height(n.left), height(n.right)); }`	`int height(Node* n) { if (!n) return 0; return 1 + max(height(n->left), height(n->right)); }`

Gotchas

Python	Go	TypeScript	C++
Deep skewed trees hit the recursion limit; `sys.setrecursionlimit` raises it but can crash if set too high. Check `root is None` before leaf checks like `not root.left`. Mutating shared `ans` is efficient; shared path lists need an undo step after recursion.	Goroutine stacks grow, but huge recursion can still exhaust memory; use an explicit stack for hostile depth. `n.Left` panics when `n` is `nil`; nil base case first.	Use `TreeNode \| null` in signatures so the null base case is honest. `Array.shift()` is costly for queues; keep a `head` index.	A skewed tree can overflow the process stack; iterative DFS avoids that risk. Check `n == nullptr` before `n->left`; leaf checks come second.

Docs: docs.python.org · pkg.go.dev · developer.mozilla.org · en.cppreference.com