Tree Selection
Traversal Method
• Left subtree → Root → Right subtree
Playback Controls
Select a tree and traversal method to begin
Traversal Methods
Use Cases:
- • Inorder: BST → sorted sequence
- • Preorder: Copy/serialize tree
- • Postorder: Delete tree, calculate size
- • Level Order: Print by levels, BFS
Legend:
Current (Inorder)
Current (Preorder)
Current (Postorder)
Current (Level Order)
Children/Subtree
Reference implementation of Binary Tree Traversals. Select a language tab to view and copy the code.
void inorder(Node* root) {
if (root == NULL) return;
inorder(root->left); // traverse left subtree
visit(root); // process current node
inorder(root->right); // traverse right subtree
}
void preorder(Node* root) {
if (root == NULL) return;
visit(root); // process current node first
preorder(root->left); // traverse left subtree
preorder(root->right); // traverse right subtree
}
void postorder(Node* root) {
if (root == NULL) return;
postorder(root->left); // traverse left subtree
postorder(root->right); // traverse right subtree
visit(root); // process current node last
}
void level_order(Node* root) {
if (!root) return;
Node* queue[MAX]; int front = 0, rear = 0;
queue[rear++] = root; // start with root
while (front < rear) {
Node* node = queue[front++]; // dequeue front
visit(node); // process current node
if (node->left) queue[rear++] = node->left;
if (node->right) queue[rear++] = node->right;
}
}void inorder(TreeNode* root) {
if (!root) return;
inorder(root->left); // traverse left subtree
visit(root); // process current node
inorder(root->right); // traverse right subtree
}
void preorder(TreeNode* root) {
if (!root) return;
visit(root); // process current node first
preorder(root->left); // traverse left subtree
preorder(root->right); // traverse right subtree
}
void postorder(TreeNode* root) {
if (!root) return;
postorder(root->left); // traverse left subtree
postorder(root->right); // traverse right subtree
visit(root); // process current node last
}
void levelOrder(TreeNode* root) {
if (!root) return;
queue<TreeNode*> q;
q.push(root); // start with root
while (!q.empty()) {
auto node = q.front(); q.pop(); // dequeue front
visit(node); // process current node
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left); // traverse left subtree
visit(root); // process current node
inorder(root.right); // traverse right subtree
}
void preorder(TreeNode root) {
if (root == null) return;
visit(root); // process current node first
preorder(root.left); // traverse left subtree
preorder(root.right); // traverse right subtree
}
void postorder(TreeNode root) {
if (root == null) return;
postorder(root.left); // traverse left subtree
postorder(root.right); // traverse right subtree
visit(root); // process current node last
}
void levelOrder(TreeNode root) {
if (root == null) return;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root); // start with root
while (!q.isEmpty()) {
TreeNode node = q.poll(); // dequeue front node
visit(node); // process current node
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
}def inorder(root):
if root is None: return
inorder(root.left) # traverse left subtree
visit(root) # process current node
inorder(root.right) # traverse right subtree
def preorder(root):
if root is None: return
visit(root) # process current node first
preorder(root.left) # traverse left subtree
preorder(root.right) # traverse right subtree
def postorder(root):
if root is None: return
postorder(root.left) # traverse left subtree
postorder(root.right) # traverse right subtree
visit(root) # process current node last
def level_order(root):
if root is None: return
queue = deque([root]) # start with root
while queue:
node = queue.popleft() # dequeue front node
visit(node) # process current node
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)function inorder(root) {
if (!root) return;
inorder(root.left); // traverse left subtree
visit(root); // process current node
inorder(root.right); // traverse right subtree
}
function preorder(root) {
if (!root) return;
visit(root); // process current node first
preorder(root.left); // traverse left subtree
preorder(root.right); // traverse right subtree
}
function postorder(root) {
if (!root) return;
postorder(root.left); // traverse left subtree
postorder(root.right); // traverse right subtree
visit(root); // process current node last
}
function levelOrder(root) {
if (!root) return;
const queue = [root]; // start with root
while (queue.length) {
const node = queue.shift(); // dequeue front node
visit(node); // process current node
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}Python — Code Walkthrough
Inorder (Left → Root → Right)
inorder(root.left) → visit(root) → inorder(root.right)Visits left subtree first, then the current node, then right. For a BST this produces sorted order.
Preorder (Root → Left → Right)
visit(root) → preorder(root.left) → preorder(root.right)Visits the current node before its children. Useful for copying or serializing a tree.
Postorder (Left → Right → Root)
postorder(root.left) → postorder(root.right) → visit(root)Visits both children before the current node. Used for deletion — children are freed before the parent.
Level Order — queue-based BFS
queue = deque([root]); node = queue.popleft()Processes nodes level by level using a FIFO queue. Each dequeued node is visited and its children are enqueued.