Grokking Algorithm Complexity and Big-O
Ask Author
Back to course home

0% completed

Vote For New Content
Binary Search Tree
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

A Binary Search Tree (BST) is a type of binary tree where each node has at most two children, and the tree maintains a specific order. For any given node:

  • The left subtree contains only nodes with values less than the node’s value.
  • The right subtree contains only nodes with values greater than the node’s value.

This property enables efficient searching, insertion, and deletion operations, making BSTs useful for various applications where ordered data needs to be stored and accessed quickly.

Image

Basic Operations on a BST and Their Complexity Analysis

1. Insertion

Python3
Python3
. . . .

Time Complexity

  1. Insertion Process:

    • Traversal: The traversal path depends on the value of the key being inserted. The function will travel down one branch of the tree, either to the left or right, at each recursive step.
    • Number of Recursive Calls:
      • In a balanced BST, the height h of the tree is approximately \log n, where n is the number of nodes. Therefore, the function will make up to O(\log n) recursive calls.
      • In an unbalanced BST (e.g., if the tree resembles a linked list), the height h can be as large as n. In this case, the function may make up to O(n) recursive calls.

Overall Time Complexity:

  • Average Case: O(\log n) for a balanced BST.
  • Worst Case: O(n) for an unbalanced BST (e.g., skewed tree).

Space Complexity

  1. Call Stack (Recursive Space):

    • The space complexity due to recursion is directly proportional to the maximum depth of the call stack.
    • In a balanced BST, the maximum depth of the recursive stack is O(\log n).
    • In an unbalanced BST, the maximum depth can reach O(n) if the tree is skewed.

  2. Auxiliary Space:

    • The function itself does not use additional space apart from the recursion stack.

Overall Space Complexity:

  • Average Case: O(\log n) for a balanced BST.
  • Worst Case: O(n) for an unbalanced BST.
Python3
Python3
. . . .

Time Complexity

  1. Search Process:
    • Traversal: At each recursive step, the function decides to move left (search(root.left, key)) or right (search(root.right, key)) based on the value of key relative to root.val.
    • Number of Recursive Calls:
      • In a balanced BST, the height h of the tree is approximately \log n, where n is the number of nodes. The function will make up to O(\log n) recursive calls in this case.
      • In an unbalanced BST (e.g., if the tree is skewed), the height h can be up to n. The function may make up to O(n) recursive calls.

Overall Time Complexity:

  • Average Case: O(\log n) for a balanced BST.
  • Worst Case: O(n) for an unbalanced BST.

Space Complexity

  1. Call Stack (Recursive Space):

    • The space complexity due to recursion is directly proportional to the maximum depth of the call stack.
    • In a balanced BST, the maximum depth of the recursive stack is O(\log n).
    • In an unbalanced BST, the maximum depth can reach O(n) if the tree is skewed.

  2. Auxiliary Space:

    • The function itself does not use any additional space beyond the call stack.

Overall Space Complexity:

  • Average Case: O(\log n) for a balanced BST.
  • Worst Case: O(n) for an unbalanced BST.

3. Deletion

Python3
Python3
. . . .

Time Complexity

  1. Traversal and Search for the Node:

    • Number of Recursive Calls:
      • In a balanced BST, the traversal depth is O(\log n), where n is the number of nodes in the tree.
      • In an unbalanced BST, the traversal depth can be up to O(n) if the tree is skewed.

  2. Deleting the Node:

    • Case 1: Node with No Children:
      • Directly removes the node by returning null.
      • Time Complexity: O(1).
    • Case 2: Node with One Child:
      • The node is replaced by its single child.
      • Time Complexity: O(1).
    • Case 3: Node with Two Children:
      • Finds the in-order successor (the smallest node in the right subtree) using the findMin method, and recursively deletes it.
      • Finding the In-order Successor: The findMin method traverses the leftmost path in the right subtree.
        • Time Complexity of findMin: O(h), where h is the height of the tree.

Overall Time Complexity:

  • Average Case: O(\log n) for a balanced BST.
  • Worst Case: O(n) for an unbalanced BST, including finding and deleting the node.

Space Complexity

  1. Call Stack (Recursive Space):

    • The space complexity depends on the recursion depth, which is proportional to the height of the tree.
    • Balanced Tree: O(\log n) space for the recursive stack.
    • Unbalanced Tree: O(n) space for the recursive stack in the worst case.

  2. Auxiliary Space:

    • The findMin method does not use any additional space other than traversing nodes.

Overall Space Complexity:

  • Average Case: O(\log n) for balanced trees.
  • Worst Case: O(n) for unbalanced trees.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible