🐍Python Programming

Trees, Binary Trees & BST

Updated 2026-05-15

30 min read

Trees, Binary Trees & BST

Introduction

Trees are a fundamental data structure used in computer science to represent hierarchical relationships between elements. They consist of nodes connected by edges and have a root node from which all other nodes descend. Understanding trees is crucial for various applications such as file systems, organization charts, and decision-making processes.

In this tutorial, we'll explore the basics of tree structures, delve into binary trees, and implement a Binary Search Tree (BST). We'll cover different types of traversals—such as inorder, preorder, postorder, and level-order—and learn how to perform essential operations like insert, search, and delete in a BST.

Core Content

What is a Tree?

A tree is a non-linear data structure that represents hierarchical relationships. It consists of nodes where each node can have zero or more child nodes. The topmost node is called the root, and any node without children is called a leaf.

Real-World Analogy

Think of a family tree as an example of a tree data structure. Each person (node) has parents and possibly children, forming a hierarchical relationship.

Binary Trees

A binary tree is a specific type of tree where each node can have at most two child nodes: a left child and a right child. This property makes binary trees particularly useful for efficient searching and sorting operations.

Real-World Analogy

Binary trees can be likened to a decision-making process, such as a game where you make choices that lead to different outcomes.

Binary Search Tree (BST)

A Binary Search Tree is a type of binary tree where each node has a key, and for every node:

The left subtree contains only nodes with keys less than the node's key.
The right subtree contains only nodes with keys greater than the node's key.
Both subtrees must also be binary search trees.

This property allows BSTs to perform efficient search, insert, and delete operations.

Implementing a Binary Tree

Let's start by implementing a basic binary tree in Python.

binary_tree.py

1class TreeNode:
2  def __init__(self, key):
3      self.left = None
4      self.right = None
5      self.val = key
6 
7# Function to insert a new node with the given key
8def insert(root, key):
9  if root is None:
10      return TreeNode(key)
11  else:
12      if root.val < key:
13          root.right = insert(root.right, key)
14      else:
15          root.left = insert(root.left, key)
16  return root
17 
18# Function to do inorder tree traversal
19def inorder_traversal(root):
20  if root:
21      inorder_traversal(root.left)
22      print(root.val, end=" ")
23      inorder_traversal(root.right)
24 
25# Driver code
26r = TreeNode(50)
27r = insert(r, 30)
28r = insert(r, 20)
29r = insert(r, 40)
30r = insert(r, 70)
31r = insert(r, 60)
32r = insert(r, 80)
33 
34print("Inorder traversal of the binary tree is:")
35inorder_traversal(r)

Output

Inorder traversal of the binary tree is:
20 30 40 50 60 70 80

Tree Traversals

Traversing a tree means visiting all its nodes in a specific order. There are several ways to traverse a binary tree:

Inorder Traversal: Left subtree, Root node, Right subtree.
Preorder Traversal: Root node, Left subtree, Right subtree.
Postorder Traversal: Left subtree, Right subtree, Root node.
Level-order Traversal (BFS): Visit nodes level by level from top to bottom.

Let's implement these traversals in Python.

tree_traversals.py

1class TreeNode:
2  def __init__(self, key):
3      self.left = None
4      self.right = None
5      self.val = key
6 
7def insert(root, key):
8  if root is None:
9      return TreeNode(key)
10  else:
11      if root.val < key:
12          root.right = insert(root.right, key)
13      else:
14          root.left = insert(root.left, key)
15  return root
16 
17# Inorder Traversal
18def inorder_traversal(root):
19  if root:
20      inorder_traversal(root.left)
21      print(root.val, end=" ")
22      inorder_traversal(root.right)
23 
24# Preorder Traversal
25def preorder_traversal(root):
26  if root:
27      print(root.val, end=" ")
28      preorder_traversal(root.left)
29      preorder_traversal(root.right)
30 
31# Postorder Traversal
32def postorder_traversal(root):
33  if root:
34      postorder_traversal(root.left)
35      postorder_traversal(root.right)
36      print(root.val, end=" ")
37 
38# Level-order Traversal (BFS)
39from collections import deque
40 
41def level_order_traversal(root):
42  if not root:
43      return
44  queue = deque([root])
45  while queue:
46      node = queue.popleft()
47      print(node.val, end=" ")
48      if node.left:
49          queue.append(node.left)
50      if node.right:
51          queue.append(node.right)
52 
53# Driver code
54r = TreeNode(50)
55r = insert(r, 30)
56r = insert(r, 20)
57r = insert(r, 40)
58r = insert(r, 70)
59r = insert(r, 60)
60r = insert(r, 80)
61 
62print("Inorder traversal of the binary tree is:")
63inorder_traversal(r)
64print("
65Preorder traversal of the binary tree is:")
66preorder_traversal(r)
67print("
68Postorder traversal of the binary tree is:")
69postorder_traversal(r)
70print("
71Level-order traversal of the binary tree is:")
72level_order_traversal(r)

Output

Inorder traversal of the binary tree is:
20 30 40 50 60 70 80 
Preorder traversal of the binary tree is:
50 30 20 40 70 60 80 
Postorder traversal of the binary tree is:
20 40 30 60 80 70 50 
Level-order traversal of the binary tree is:
50 30 70 20 40 60 80

Binary Search Tree Operations

Now, let's implement a BST and perform basic operations like insert, search, and delete.

bst_operations.py

1class TreeNode:
2  def __init__(self, key):
3      self.left = None
4      self.right = None
5      self.val = key
6 
7def insert(root, key):
8  if root is None:
9      return TreeNode(key)
10  else:
11      if root.val < key:
12          root.right = insert(root.right, key)
13      else:
14          root.left = insert(root.left, key)
15  return root
16 
17def search(root, key):
18  if root is None or root.val == key:
19      return root
20  if root.val < key:
21      return search(root.right, key)
22  return search(root.left, key)
23 
24def delete_node(root, key):
25  if root is None:
26      return root
27  if key < root.val:
28      root.left = delete_node(root.left, key)
29  elif key > root.val:
30      root.right = delete_node(root.right, key)
31  else:
32      if root.left is None:
33          temp = root.right
34          root = None
35          return temp
36      elif root.right is None:
37          temp = root.left
38          root = None
39          return temp
40      temp = minValueNode(root.right)
41      root.val = temp.val
42      root.right = delete_node(root.right, temp.val)
43  return root
44 
45def minValueNode(node):
46  current = node
47  while current.left is not None:
48      current = current.left
49  return current
50 
51# Driver code
52r = TreeNode(50)
53r = insert(r, 30)
54r = insert(r, 20)
55r = insert(r, 40)
56r = insert(r, 70)
57r = insert(r, 60)
58r = insert(r, 80)
59 
60print("Inorder traversal of the BST is:")
61inorder_traversal(r)
62 
63key = 20
64if search(r, key):
65  print(f"
66{key} found in the BST.")
67else:
68  print(f"
69{key} not found in the BST.")
70 
71r = delete_node(r, 20)
72print("
73Inorder traversal after deleting 20:")
74inorder_traversal(r)
75 
76r = delete_node(r, 30)
77print("
78Inorder traversal after deleting 30:")
79inorder_traversal(r)
80 
81r = delete_node(r, 50)
82print("
83Inorder traversal after deleting 50:")
84inorder_traversal(r)

Output

Inorder traversal of the BST is:
20 30 40 50 60 70 80 
20 found in the BST.
Inorder traversal after deleting 20:
30 40 50 60 70 80 
Inorder traversal after deleting 30:
40 50 60 70 80 
Inorder traversal after deleting 50:
40 60 70 80

Common Mistakes and Pitfalls

Forgetting to handle the case where a node has two children: In deletion, if a node has both left and right children, you must find the inorder successor (smallest in the right subtree) or predecessor (largest in the left subtree).
Incorrect traversal logic: Ensure that each traversal method visits nodes in the correct order.
Not checking for None values: Always check if a node is None before accessing its properties to avoid errors.

Practical Example

Let's create a complete program that allows users to insert, search, and delete elements in a BST.

bst_practical.py

1class TreeNode:
2  def __init__(self, key):
3      self.left = None
4      self.right = None
5      self.val = key
6 
7def insert(root, key):
8  if root is None:
9      return TreeNode(key)
10  else:
11      if root.val < key:
12          root.right = insert(root.right, key)
13      else:
14          root.left = insert(root.left, key)
15  return root
16 
17def search(root, key):
18  if root is None or root.val == key:
19      return root
20  if root.val < key:
21      return search(root.right, key)
22  return search(root.left, key)
23 
24def delete_node(root, key):
25  if root is None:
26      return root
27  if key < root.val:
28      root.left = delete_node(root.left, key)
29  elif key > root.val:
30      root.right = delete_node(root.right, key)
31  else:
32      if root.left is None:
33          temp = root.right
34          root = None
35          return temp
36      elif root.right is None:
37          temp = root.left
38          root = None
39          return temp
40      temp = minValueNode(root.right)
41      root.val = temp.val
42      root.right = delete_node(root.right, temp.val)
43  return root
44 
45def minValueNode(node):
46  current = node
47  while current.left is not None:
48      current = current.left
49  return current
50 
51def inorder_traversal(root):
52  if root:
53      inorder_traversal(root.left)
54      print(root.val, end=" ")
55      inorder_traversal(root.right)
56 
57# Driver code
58r = TreeNode(50)
59r = insert(r, 30)
60r = insert(r, 20)
61r = insert(r, 40)
62r = insert(r, 70)
63r = insert(r, 60)
64r = insert(r, 80)
65 
66print("Inorder traversal of the BST is:")
67inorder_traversal(r)
68 
69key = 20
70if search(r, key):
71  print(f"
72{key} found in the BST.")
73else:
74  print(f"
75{key} not found in the BST.")
76 
77r = delete_node(r, 20)
78print("
79Inorder traversal after deleting 20:")
80inorder_traversal(r)
81 
82r = delete_node(r, 30)
83print("
84Inorder traversal after deleting 30:")
85inorder_traversal(r)
86 
87r = delete_node(r, 50)
88print("
89Inorder traversal after deleting 50:")
90inorder_traversal(r)

Summary

Concept	Description
Tree	A hierarchical data structure with nodes connected by edges.
Binary Tree	Each node has at most two child nodes: left and right.
Binary Search Tree (BST)	A binary tree where the left subtree contains only smaller keys, and the right subtree contains only larger keys.
Inorder Traversal	Visits nodes in this order: Left subtree, Root node, Right subtree.
Preorder Traversal	Visits nodes in this order: Root node, Left subtree, Right subtree.
Postorder Traversal	Visits nodes in this order: Left subtree, Right subtree, Root node.
Level-order Traversal (BFS)	Visits nodes level by level from top to bottom.

What's Next?

In the next topic, we'll explore graphs and hash tables, two more essential data structures in computer science. Graphs are used to model relationships between objects, while hash tables provide efficient key-value storage and retrieval.

Stay tuned for more insights into these powerful data structures!

Tip

Understanding trees is crucial for many advanced algorithms and data processing tasks. Practice implementing different types of trees and their operations to solidify your knowledge.

🐍Python Programming

Trees, Binary Trees & BST

Updated 2026-05-15

30 min read

Trees, Binary Trees & BST

Introduction

Core Content

What is a Tree?

Real-World Analogy

Think of a family tree as an example of a tree data structure. Each person (node) has parents and possibly children, forming a hierarchical relationship.

Binary Trees

Real-World Analogy

Binary trees can be likened to a decision-making process, such as a game where you make choices that lead to different outcomes.

Binary Search Tree (BST)

A Binary Search Tree is a type of binary tree where each node has a key, and for every node:

The left subtree contains only nodes with keys less than the node's key.
The right subtree contains only nodes with keys greater than the node's key.
Both subtrees must also be binary search trees.

This property allows BSTs to perform efficient search, insert, and delete operations.

Implementing a Binary Tree

Let's start by implementing a basic binary tree in Python.

binary_tree.py

1class TreeNode:
2  def __init__(self, key):
3      self.left = None
4      self.right = None
5      self.val = key
6 
7# Function to insert a new node with the given key
8def insert(root, key):
9  if root is None:
10      return TreeNode(key)
11  else:
12      if root.val < key:
13          root.right = insert(root.right, key)
14      else:
15          root.left = insert(root.left, key)
16  return root
17 
18# Function to do inorder tree traversal
19def inorder_traversal(root):
20  if root:
21      inorder_traversal(root.left)
22      print(root.val, end=" ")
23      inorder_traversal(root.right)
24 
25# Driver code
26r = TreeNode(50)
27r = insert(r, 30)
28r = insert(r, 20)
29r = insert(r, 40)
30r = insert(r, 70)
31r = insert(r, 60)
32r = insert(r, 80)
33 
34print("Inorder traversal of the binary tree is:")
35inorder_traversal(r)

Output

Inorder traversal of the binary tree is:
20 30 40 50 60 70 80

Tree Traversals

Traversing a tree means visiting all its nodes in a specific order. There are several ways to traverse a binary tree:

Inorder Traversal: Left subtree, Root node, Right subtree.
Preorder Traversal: Root node, Left subtree, Right subtree.
Postorder Traversal: Left subtree, Right subtree, Root node.
Level-order Traversal (BFS): Visit nodes level by level from top to bottom.

Let's implement these traversals in Python.

tree_traversals.py

1class TreeNode:
2  def __init__(self, key):
3      self.left = None
4      self.right = None
5      self.val = key
6 
7def insert(root, key):
8  if root is None:
9      return TreeNode(key)
10  else:
11      if root.val < key:
12          root.right = insert(root.right, key)
13      else:
14          root.left = insert(root.left, key)
15  return root
16 
17# Inorder Traversal
18def inorder_traversal(root):
19  if root:
20      inorder_traversal(root.left)
21      print(root.val, end=" ")
22      inorder_traversal(root.right)
23 
24# Preorder Traversal
25def preorder_traversal(root):
26  if root:
27      print(root.val, end=" ")
28      preorder_traversal(root.left)
29      preorder_traversal(root.right)
30 
31# Postorder Traversal
32def postorder_traversal(root):
33  if root:
34      postorder_traversal(root.left)
35      postorder_traversal(root.right)
36      print(root.val, end=" ")
37 
38# Level-order Traversal (BFS)
39from collections import deque
40 
41def level_order_traversal(root):
42  if not root:
43      return
44  queue = deque([root])
45  while queue:
46      node = queue.popleft()
47      print(node.val, end=" ")
48      if node.left:
49          queue.append(node.left)
50      if node.right:
51          queue.append(node.right)
52 
53# Driver code
54r = TreeNode(50)
55r = insert(r, 30)
56r = insert(r, 20)
57r = insert(r, 40)
58r = insert(r, 70)
59r = insert(r, 60)
60r = insert(r, 80)
61 
62print("Inorder traversal of the binary tree is:")
63inorder_traversal(r)
64print("
65Preorder traversal of the binary tree is:")
66preorder_traversal(r)
67print("
68Postorder traversal of the binary tree is:")
69postorder_traversal(r)
70print("
71Level-order traversal of the binary tree is:")
72level_order_traversal(r)

Output

Inorder traversal of the binary tree is:
20 30 40 50 60 70 80 
Preorder traversal of the binary tree is:
50 30 20 40 70 60 80 
Postorder traversal of the binary tree is:
20 40 30 60 80 70 50 
Level-order traversal of the binary tree is:
50 30 70 20 40 60 80

Binary Search Tree Operations

Now, let's implement a BST and perform basic operations like insert, search, and delete.

bst_operations.py

1class TreeNode:
2  def __init__(self, key):
3      self.left = None
4      self.right = None
5      self.val = key
6 
7def insert(root, key):
8  if root is None:
9      return TreeNode(key)
10  else:
11      if root.val < key:
12          root.right = insert(root.right, key)
13      else:
14          root.left = insert(root.left, key)
15  return root
16 
17def search(root, key):
18  if root is None or root.val == key:
19      return root
20  if root.val < key:
21      return search(root.right, key)
22  return search(root.left, key)
23 
24def delete_node(root, key):
25  if root is None:
26      return root
27  if key < root.val:
28      root.left = delete_node(root.left, key)
29  elif key > root.val:
30      root.right = delete_node(root.right, key)
31  else:
32      if root.left is None:
33          temp = root.right
34          root = None
35          return temp
36      elif root.right is None:
37          temp = root.left
38          root = None
39          return temp
40      temp = minValueNode(root.right)
41      root.val = temp.val
42      root.right = delete_node(root.right, temp.val)
43  return root
44 
45def minValueNode(node):
46  current = node
47  while current.left is not None:
48      current = current.left
49  return current
50 
51# Driver code
52r = TreeNode(50)
53r = insert(r, 30)
54r = insert(r, 20)
55r = insert(r, 40)
56r = insert(r, 70)
57r = insert(r, 60)
58r = insert(r, 80)
59 
60print("Inorder traversal of the BST is:")
61inorder_traversal(r)
62 
63key = 20
64if search(r, key):
65  print(f"
66{key} found in the BST.")
67else:
68  print(f"
69{key} not found in the BST.")
70 
71r = delete_node(r, 20)
72print("
73Inorder traversal after deleting 20:")
74inorder_traversal(r)
75 
76r = delete_node(r, 30)
77print("
78Inorder traversal after deleting 30:")
79inorder_traversal(r)
80 
81r = delete_node(r, 50)
82print("
83Inorder traversal after deleting 50:")
84inorder_traversal(r)

Output

Inorder traversal of the BST is:
20 30 40 50 60 70 80 
20 found in the BST.
Inorder traversal after deleting 20:
30 40 50 60 70 80 
Inorder traversal after deleting 30:
40 50 60 70 80 
Inorder traversal after deleting 50:
40 60 70 80

Common Mistakes and Pitfalls

Forgetting to handle the case where a node has two children: In deletion, if a node has both left and right children, you must find the inorder successor (smallest in the right subtree) or predecessor (largest in the left subtree).
Incorrect traversal logic: Ensure that each traversal method visits nodes in the correct order.
Not checking for None values: Always check if a node is None before accessing its properties to avoid errors.

Practical Example

Let's create a complete program that allows users to insert, search, and delete elements in a BST.

bst_practical.py

1class TreeNode:
2  def __init__(self, key):
3      self.left = None
4      self.right = None
5      self.val = key
6 
7def insert(root, key):
8  if root is None:
9      return TreeNode(key)
10  else:
11      if root.val < key:
12          root.right = insert(root.right, key)
13      else:
14          root.left = insert(root.left, key)
15  return root
16 
17def search(root, key):
18  if root is None or root.val == key:
19      return root
20  if root.val < key:
21      return search(root.right, key)
22  return search(root.left, key)
23 
24def delete_node(root, key):
25  if root is None:
26      return root
27  if key < root.val:
28      root.left = delete_node(root.left, key)
29  elif key > root.val:
30      root.right = delete_node(root.right, key)
31  else:
32      if root.left is None:
33          temp = root.right
34          root = None
35          return temp
36      elif root.right is None:
37          temp = root.left
38          root = None
39          return temp
40      temp = minValueNode(root.right)
41      root.val = temp.val
42      root.right = delete_node(root.right, temp.val)
43  return root
44 
45def minValueNode(node):
46  current = node
47  while current.left is not None:
48      current = current.left
49  return current
50 
51def inorder_traversal(root):
52  if root:
53      inorder_traversal(root.left)
54      print(root.val, end=" ")
55      inorder_traversal(root.right)
56 
57# Driver code
58r = TreeNode(50)
59r = insert(r, 30)
60r = insert(r, 20)
61r = insert(r, 40)
62r = insert(r, 70)
63r = insert(r, 60)
64r = insert(r, 80)
65 
66print("Inorder traversal of the BST is:")
67inorder_traversal(r)
68 
69key = 20
70if search(r, key):
71  print(f"
72{key} found in the BST.")
73else:
74  print(f"
75{key} not found in the BST.")
76 
77r = delete_node(r, 20)
78print("
79Inorder traversal after deleting 20:")
80inorder_traversal(r)
81 
82r = delete_node(r, 30)
83print("
84Inorder traversal after deleting 30:")
85inorder_traversal(r)
86 
87r = delete_node(r, 50)
88print("
89Inorder traversal after deleting 50:")
90inorder_traversal(r)

Summary

Concept	Description
Tree	A hierarchical data structure with nodes connected by edges.
Binary Tree	Each node has at most two child nodes: left and right.
Binary Search Tree (BST)	A binary tree where the left subtree contains only smaller keys, and the right subtree contains only larger keys.
Inorder Traversal	Visits nodes in this order: Left subtree, Root node, Right subtree.
Preorder Traversal	Visits nodes in this order: Root node, Left subtree, Right subtree.
Postorder Traversal	Visits nodes in this order: Left subtree, Right subtree, Root node.
Level-order Traversal (BFS)	Visits nodes level by level from top to bottom.

What's Next?

Stay tuned for more insights into these powerful data structures!

Tip

Understanding trees is crucial for many advanced algorithms and data processing tasks. Practice implementing different types of trees and their operations to solidify your knowledge.