GeezerVison

A clear advantage with Binary Search Trees is that operations like search, delete, and insert are fast and done without having to shift values in memory.

Binary Search Trees

A Binary Search Tree (BST) is a type of Binary Tree data structure, where the following properties must be true for any node "X" in the tree:

The X node's left child and all of its descendants (children, children's children, and so on) have lower values than X's value.
The right child, and all its descendants have higher values than X's value.
Left and right subtrees must also be Binary Search Trees.

These properties makes it faster to search, add and delete values than a regular binary tree.

To make this as easy to understand and implement as possible, let's also assume that all values in a Binary Search Tree are unique.

The size of a tree is the number of nodes in it (n).

A subtree starts with one of the nodes in the tree as a local root, and consists of that node and all its descendants.

The descendants of a node are all the child nodes of that node, and all their child nodes, and so on. Just start with a node, and the descendants will be all nodes that are connected below that node.

The node's height is the maximum number of edges between that node and a leaf node.

A node's in-order successor is the node that comes after it if we were to do in-order traversal. In-order traversal of the BST above would result in node 13 coming before node 14, and so the successor of node 13 is node 14.

Traversal of a Binary Search Tree

Just to confirm that we actually have a Binary Search Tree data structure in front of us, we can check if the properties at the top of this page are true. So for every node in the figure above, check if all the values to the left of the node are lower, and that all values to the right are higher.

Another way to check if a Binary Tree is BST, is to do an in-order traversal (like we did on the previous page) and check if the resulting list of values are in an increasing order.

The code below is an implementation of the Binary Search Tree in the figure above, with traversal.

Example

Traversal of a Binary Search Tree in Python

class TreeNode:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None

def inOrderTraversal(node):
  if node is None:
    return
  inOrderTraversal(node.left)
  print(node.data, end=", ")
  inOrderTraversal(node.right)

root = TreeNode(13)
node7 = TreeNode(7)
node15 = TreeNode(15)
node3 = TreeNode(3)
node8 = TreeNode(8)
node14 = TreeNode(14)
node19 = TreeNode(19)
node18 = TreeNode(18)

root.left = node7
root.right = node15

node7.left = node3
node7.right = node8

node15.left = node14
node15.right = node19

node19.left = node18

# Traverse
inOrderTraversal(root)

Try it Yourself »

As we can see by running the code example above, the in-order traversal produces a list of numbers in an increasing (ascending) order, which means that this Binary Tree is a Binary Search Tree.

Search for a Value in a BST

Searching for a value in a BST is very similar to how we found a value using Binary Search on an array.

For Binary Search to work, the array must be sorted already, and searching for a value in an array can then be done really fast.

Similarly, searching for a value in a BST can also be done really fast because of how the nodes are placed.

How it works:

Start at the root node.
If this is the value we are looking for, return.
If the value we are looking for is higher, continue searching in the right subtree.
If the value we are looking for is lower, continue searching in the left subtree.
If the subtree we want to search does not exist, depending on the programming language, return None, or NULL, or something similar, to indicate that the value is not inside the BST.

The algorithm can be implemented like this:

Example

Search the Tree for the value "13"

def search(node, target):
  if node is None:
    return None
  elif node.data == target:
    return node
  elif target < node.data:
    return search(node.left, target)
  else:
    return search(node.right, target)

# Search for a value
result = search(root, 13)
if result:
  print(f"Found the node with value: {result.data}")
else:
  print("Value not found in the BST.")

Try it Yourself »

The time complexity for searching a BST for a value is O(h), where h is the height of the tree.

For a BST with most nodes on the right side for example, the height of the tree becomes larger than it needs to be, and the worst case search will take longer. Such trees are called unbalanced.

Balanced BST

Unbalanced BST

Both Binary Search Trees above have the same nodes, and in-order traversal of both trees gives us the same result but the height is very different. It takes longer time to search the unbalanced tree above because it is higher.

We will use the next page to describe a type of Binary Tree called AVL Trees. AVL trees are self-balancing, which means that the height of the tree is kept to a minimum so that operations like search, insertion and deletion take less time.

Insert a Node in a BST

Inserting a node in a BST is similar to searching for a value.

How it works:

Start at the root node.
Compare each node:
- Is the value lower? Go left.
- Is the value higher? Go right.
Continue to compare nodes with the new value until there is no right or left to compare with. That is where the new node is inserted.

Inserting nodes as described above means that an inserted node will always become a new leaf node.

All nodes in the BST are unique, so in case we find the same value as the one we want to insert, we do nothing.

This is how node insertion in BST can be implemented:

Example

Inserting a node in a BST:

def insert(node, data):
  if node is None:
    return TreeNode(data)
  else:
    if data < node.data:
      node.left = insert(node.left, data)
    elif data > node.data:
      node.right = insert(node.right, data)
  return node

# Inserting new value into the BST
insert(root, 10)

Try it Yourself »

Find The Lowest Value in a BST Subtree

The next section will explain how we can delete a node in a BST, but to do that we need a function that finds the lowest value in a node's subtree.

How it works:

Start at the root node of the subtree.
Go left as far as possible.
The node you end up in is the node with the lowest value in that BST subtree.

This is how a function for finding the lowest value in the subtree of a BST node looks like:

Example

Find the lowest value in a BST subtree

def minValueNode(node):
  current = node
  while current.left is not None:
    current = current.left
  return current

# Find Lowest
print("\nLowest value:",minValueNode(root).data)

Try it Yourself »

We will use this minValueNode() function in the section below, to find a node's in-order successor, and use that to delete a node.

Delete a Node in a BST

To delete a node, our function must first search the BST to find it.

After the node is found there are three different cases where deleting a node must be done differently.

How it works:

If the node is a leaf node, remove it by removing the link to it.
If the node only has one child node, connect the parent node of the node you want to remove to that child node.
If the node has both right and left child nodes: Find the node's in-order successor, change values with that node, then delete it.

In step 3 above, the successor we find will always be a leaf node, and because it is the node that comes right after the node we want to delete, we can swap values with it and delete it.

This is how a BST can be implemented with functionality for deleting a node:

Example

Delete a Node in a BST

def delete(node, data):
  if not node:
    return None

  if data < node.data:
    node.left = delete(node.left, data)
  elif data > node.data:
    node.right = delete(node.right, data)
  else:
    # Node with only one child or no child
    if not node.left:
      temp = node.right
      node = None
      return temp
    elif not node.right:
      temp = node.left
      node = None
      return temp

    # Node with two children, get the in-order successor
    node.data = minValueNode(node.right).data
    node.right = delete(node.right, node.data)

  return node

# Delete node 15
delete(root,15)

Try it Yourself »

Line 1: The node argument here makes it possible for the function to call itself recursively on smaller and smaller subtrees in the search for the node with the data we want to delete.

Line 2-8: This is searching for the node with correct data that we want to delete.

Line 9-22: The node we want to delete has been found. There are three such cases:

Case 1: Node with no child nodes (leaf node). None is returned, and that becomes the parent node's new left or right value by recursion (line 6 or 8).
Case 2: Node with either left or right child node. That left or right child node becomes the parent's new left or right child through recursion (line 7 or 9).
Case 3: Node has both left and right child nodes. The in-order successor is found using the minValueNode() function. We keep the successor's value by setting it as the value of the node we want to delete, and then we can delete the successor node.

Line 24: node is returned to maintain the recursive functionality.

BST Compared to Other Data Structures

Binary Search Trees take the best from two other data structures: Arrays and Linked Lists.

Data Structure	Searching for a value	Delete / Insert leads to shifting in memory
Sorted Array	`O(\log n)`	Yes
Linked List	`O(n)`	No
Binary Search Tree	`O(\log n)`	No

Searching a BST is just as fast as Binary Search on an array, with the same time complexity O(log n).

And deleting and inserting new values can be done without shifting elements in memory, just like with Linked Lists.

BST Balance and Time Complexity

On a Binary Search Tree, operations like inserting a new node, deleting a node, or searching for a node are actually O(h). That means that the higher the tree is (h), the longer the operation will take.

The reason why we wrote that searching for a value is O(log n) in the table above is because that is true if the tree is "balanced", like in the image below.

Balanced BST

We call this tree balanced because there are approximately the same number of nodes on the left and right side of the tree.

The exact way to tell that a Binary Tree is balanced is that the height of the left and right subtrees of any node only differs by one. In the image above, the left subtree of the root node has height h=2, and the right subtree has height h=3.

For a balanced BST, with a large number of nodes (big n), we get height h ≈ \log_2 n, and therefore the time complexity for searching, deleting, or inserting a node can be written as O(h) = O(\log n).

But, in case the BST is completely unbalanced, like in the image below, the height of the tree is approximately the same as the number of nodes, h ≈ n, and we get time complexity O(h) = O(n) for searching, deleting, or inserting a node.

Unbalanced BST

So, to optimize operations on a BST, the height must be minimized, and to do that the tree must be balanced.

And keeping a Binary Search Tree balanced is exactly what AVL Trees do, which is the data structure explained on the next page.

❮ Previous Next ❯

★ +1

W3Schools Full Access - your next career move

REMOVE ADS

Learn more about Adventure Mode›

Free account

Track your progress

XP earned 0 Day streak 0 Spaces 0 League —

New

Learn in Adventure Mode W3Schools Adventure App

Coding fundamentals as bite-sized lessons and challenges.

Contact Sales

If you want to use W3Schools services as an educational institution, team or enterprise, send us an e-mail:
[email protected]

Report Error

If you want to report an error, or if you want to make a suggestion, send us an e-mail:
[email protected]

   

FORUM ABOUT CAMPUS

W3Schools is optimized for learning and training. Examples might be simplified to improve reading and learning.
Tutorials, references, and examples are constantly reviewed to avoid errors, but we cannot warrant full correctness
of all content. While using W3Schools, you agree to have read and accepted our terms of use, cookies and privacy policy.

Copyright 1999-2026 by Refsnes Data. All Rights Reserved. W3Schools is Powered by W3.CSS.

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

GeezerVison

Python Tutorial

Python Classes

File Handling

Python Modules

Python Matplotlib

Machine Learning

Python DSA

Python MySQL

Python MongoDB

Python Cert

Python How To

Python Examples

Python Reference

Module Reference

Python Binary Search Trees

Binary Search Trees

Traversal of a Binary Search Tree

Example

Search for a Value in a BST

Example

Insert a Node in a BST

Example

Find The Lowest Value in a BST Subtree

Example

Delete a Node in a BST

Example

BST Compared to Other Data Structures

BST Balance and Time Complexity

Track your progress

Learn in Adventure Mode W3Schools Adventure App

Contact Sales

Report Error

Top Tutorials

Top References

Top Examples

Get Certified