Binary Trees
A binary tree is a tree data structure in which each node has at most two children, referred to the left and right child of the node. This page covers properties of binary trees and common algorithms that can be applied to binary trees for the coding interview.
Properties of Binary Trees
The top node of a binary tree is called the root. Each node in a binary tree can have at most two children, referred to as the left child and right child. A node that does not have any children is called a leaf node:
Height of a Binary Tree
The height of a binary tree is the number of edges on the longest path between the root node and a leaf node. This is also known as the depth of the tree.
Balanced Binary Tree
A binary tree is balanced if the height of the left and right subtrees of every node differ by at most 1.
Complete Binary Tree
A binary tree is complete if every level, except possibly the last, is completely filled, and all nodes are as far left as possible. Complete binary trees are an important concept in heap data structures.
A complete binary tree has a height of O(log(n)), where n is the number of nodes in the tree.
Binary Search Tree
A binary search tree (BST) is a binary tree where:
- All nodes in the left subtree of the root have a value less than the root.
- All nodes in the right subtree of the root have a value greater than the root.
The same property applies to all subtrees in the tree. This property allows for efficient search, insertion, and deletion of nodes in the tree.
Pre-Order Traversal
In a pre-order traversal, the root node is visited first, followed by the left subtree, and then the right subtree. The same order is repeated for each subtree. This corresponds to the order in which nodes are added to the call stack during a recursive traversal.
Pre-order traversals are useful for copying a tree, as the order of nodes is preserved.
Animated Pre-Order Traversal
Visualization
Python
def preOrderTraversal(root):if root is None:returnprint(root.val)preOrderTraversal(root.left)preOrderTraversal(root.right)
pre-order traversal
0 / 52
In-Order Traversal
In an In-Order traversal, the left subtree is visited first, followed by the root node, and then the right subtree.
In-Order Traversal on a Binary Search Tree (BST)
Note that an In-order traversal on a binary search tree (BST) like the one shown below will give you the nodes in sorted order.
Animated In-Order Traversal
Visualization
Python
def inOrderTraversal(root):if root is None:returninOrderTraversal(root.left)print(root.val)inOrderTraversal(root.right)
in-order traversal
0 / 52
Post-Order Traversal
In a post-order traversal, the left subtree is visited first, followed by the right subtree, and then the root node. This corresponds to the order in which nodes are popped off the call stack during a recursive traversal.
A post-order traversal is useful for deleting nodes from a tree, as it ensures that a parent node is deleted after its children.
Animated Post-Order Traversal
Visualization
Python
def postOrderTraversal(root):if root is None:returnpostOrderTraversal(root.left)postOrderTraversal(root.right)print(root.val)
post-order traversal
0 / 52
Summary
| Traversal | Order | Notes |
|---|---|---|
| Pre-Order | Root, Left, Right | Root before children |
| In-Order | Left, Root, Right | In-Order on a BST gives nodes in sorted order |
| Post-Order | Left, Right, Root | Children before root |
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.