Card 06/ 08
Binary Tree Traversals in Python, Java and TypeScript
A node class, the three recursive orders, level order and height in each language.
A binary tree in code is a node type with a value and two links, plus functions that walk it. This card covers one implementation in each of Python, Java and TypeScript: the node, the three depth-first traversals, a level-order traversal with a queue, and height counted in edges.
Each listing builds the tree used throughout this topic: the root 1 with children 2 and 3, node 2 with children 4 and 5, node 3 with only a right child, 6, and node 6 with only a left child, 7. Python uses a small class, Java a record, a class whose fields are fixed when it is created, and TypeScript a plain object type whose links are null when empty. The three depth-first traversals are separate functions, each with its visit line, highlighted, in a different place. Level order takes the front of a queue on each turn, also highlighted. Python's deque and Java's ArrayDeque remove from the front in O(1) time. TypeScript keeps an index to the front of an ordinary array instead of calling shift, which moves every remaining item along and can make each removal O(n). Height returns -1 for the empty tree. Each listing was run.
One binary tree's traversals and height, in each language
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def pre_order(node, visited):
if node is not None:
visited.append(node.value)
pre_order(node.left, visited)
pre_order(node.right, visited)
def in_order(node, visited):
if node is not None:
in_order(node.left, visited)
visited.append(node.value)
in_order(node.right, visited)
def post_order(node, visited):
if node is not None:
post_order(node.left, visited)
post_order(node.right, visited)
visited.append(node.value)
def level_order(root):
visited = []
queue = deque([root] if root is not None else [])
while queue:
node = queue.popleft()
visited.append(node.value)
for child in (node.left, node.right):
if child is not None:
queue.append(child)
return visited
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6, Node(7))))
for name, traverse in (("pre-order", pre_order), ("in-order", in_order), ("post-order", post_order)):
visited = []
traverse(root, visited)
print(f"{name}:", *visited)
print("level order:", *level_order(root))
print("height:", height(root))pre-order: 1 2 4 5 3 6 7
in-order: 4 2 5 1 3 7 6
post-order: 4 5 2 7 6 3 1
level order: 1 2 3 4 5 6 7
height: 3import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
public class BinaryTreeCode {
record Node(int value, Node left, Node right) {
Node(int value) {
this(value, null, null);
}
}
static void preOrder(Node node, List<Integer> visited) {
if (node != null) {
visited.add(node.value());
preOrder(node.left(), visited);
preOrder(node.right(), visited);
}
}
static void inOrder(Node node, List<Integer> visited) {
if (node != null) {
inOrder(node.left(), visited);
visited.add(node.value());
inOrder(node.right(), visited);
}
}
static void postOrder(Node node, List<Integer> visited) {
if (node != null) {
postOrder(node.left(), visited);
postOrder(node.right(), visited);
visited.add(node.value());
}
}
static List<Integer> levelOrder(Node root) {
List<Integer> visited = new ArrayList<>();
ArrayDeque<Node> queue = new ArrayDeque<>();
if (root != null) {
queue.addLast(root);
}
while (!queue.isEmpty()) {
Node node = queue.pollFirst();
visited.add(node.value());
if (node.left() != null) {
queue.addLast(node.left());
}
if (node.right() != null) {
queue.addLast(node.right());
}
}
return visited;
}
static int height(Node node) {
if (node == null) {
return -1;
}
return 1 + Math.max(height(node.left()), height(node.right()));
}
static String spaced(List<Integer> values) {
return String.join(" ", values.stream().map(String::valueOf).toList());
}
public static void main(String[] args) {
Node root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, null, new Node(6, new Node(7), null)));
List<Integer> pre = new ArrayList<>();
List<Integer> in = new ArrayList<>();
List<Integer> post = new ArrayList<>();
preOrder(root, pre);
inOrder(root, in);
postOrder(root, post);
System.out.println("pre-order: " + spaced(pre));
System.out.println("in-order: " + spaced(in));
System.out.println("post-order: " + spaced(post));
System.out.println("level order: " + spaced(levelOrder(root)));
System.out.println("height: " + height(root));
}
}pre-order: 1 2 4 5 3 6 7
in-order: 4 2 5 1 3 7 6
post-order: 4 5 2 7 6 3 1
level order: 1 2 3 4 5 6 7
height: 3type TreeNode = { value: number; left: TreeNode | null; right: TreeNode | null };
const node = (value: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode => ({
value,
left,
right,
});
function preOrder(current: TreeNode | null, visited: number[]): void {
if (current !== null) {
visited.push(current.value);
preOrder(current.left, visited);
preOrder(current.right, visited);
}
}
function inOrder(current: TreeNode | null, visited: number[]): void {
if (current !== null) {
inOrder(current.left, visited);
visited.push(current.value);
inOrder(current.right, visited);
}
}
function postOrder(current: TreeNode | null, visited: number[]): void {
if (current !== null) {
postOrder(current.left, visited);
postOrder(current.right, visited);
visited.push(current.value);
}
}
function levelOrder(root: TreeNode | null): number[] {
const visited: number[] = [];
const queue: TreeNode[] = root === null ? [] : [root];
let front = 0;
while (front < queue.length) {
const current = queue[front++];
visited.push(current.value);
if (current.left !== null) queue.push(current.left);
if (current.right !== null) queue.push(current.right);
}
return visited;
}
function height(current: TreeNode | null): number {
if (current === null) {
return -1;
}
return 1 + Math.max(height(current.left), height(current.right));
}
const root = node(1, node(2, node(4), node(5)), node(3, null, node(6, node(7))));
for (const [name, traverse] of [
["pre-order", preOrder],
["in-order", inOrder],
["post-order", postOrder],
] as const) {
const visited: number[] = [];
traverse(root, visited);
console.log(`${name}: ${visited.join(" ")}`);
}
console.log(`level order: ${levelOrder(root).join(" ")}`);
console.log(`height: ${height(root)}`);pre-order: 1 2 4 5 3 6 7
in-order: 4 2 5 1 3 7 6
post-order: 4 5 2 7 6 3 1
level order: 1 2 3 4 5 6 7
height: 3All three printed the same five lines: pre-order 1 2 4 5 3 6 7, in-order 4 2 5 1 3 7 6, post-order 4 5 2 7 6 3 1, level order 1 2 3 4 5 6 7, and a height of 3.
Every traversal takes O(n) time on n nodes, because each node is visited once. Their extra memory differs. The recursive orders hold one frame per node on the current path, so they need room in proportion to the height, which ranges from about log n in a tree with every level full to n in a tree shaped like a chain. Level order holds up to one level in its queue, so its memory follows the widest level instead. A recursive traversal of a chain thousands of nodes long can exhaust the call stack in all three languages, and a version with an explicit stack avoids that.
The Java record makes the tree immutable, so it is built from the leaves up in one expression. Python's class and TypeScript's object can have links changed later, which later structures that insert and remove nodes depend on.
← → move through sections and cards