BST

Binary Search Trees (BSTs) in Java

Binary Search Trees (BSTs) are a fundamental data structure in Java and are widely used in Leetcode problems. A BST is a binary tree where each node has at most two children, and for each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node.

Table of Contents

1. BST Basics
2. Common BST Operations
3. Tree Traversal Techniques
4. Common Leetcode Patterns
5. Time and Space Complexity
6. Related Leetcode Questions

BST Basics

• Definition: A Binary Search Tree (BST) is a binary tree where each node has at most two children, and for each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node.
• Declaration:

  class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

• Key Characteristics:
  • Each node has at most two children.
  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Common BST Operations

1. Inserting a Node

• Example:

  public TreeNode insert(TreeNode root, int val) {
      if (root == null) {
          return new TreeNode(val);
      }
      if (val < root.val) {
          root.left = insert(root.left, val);
      } else {
          root.right = insert(root.right, val);
      }
      return root;
  }

• Time Complexity: O(n) (worst case for unbalanced tree), O(log n) (average case for balanced tree)
• Space Complexity: O(n) (worst case for unbalanced tree), O(log n) (average case for balanced tree)

2. Searching for a Node

• Example:

  public TreeNode search(TreeNode root, int val) {
      if (root == null || root.val == val) {
          return root;
      }
      if (val < root.val) {
          return search(root.left, val);
      } else {
          return search(root.right, val);
      }
  }

• Time Complexity: O(n) (worst case for unbalanced tree), O(log n) (average case for balanced tree)
• Space Complexity: O(n) (worst case for unbalanced tree), O(log n) (average case for balanced tree)

3. Deleting a Node

• Example:

  public TreeNode delete(TreeNode root, int val) {
      if (root == null) {
          return null;
      }
      if (val < root.val) {
          root.left = delete(root.left, val);
      } else if (val > root.val) {
          root.right = delete(root.right, val);
      } else {
          if (root.left == null) {
              return root.right;
          } else if (root.right == null) {
              return root.left;
          }
          TreeNode minNode = findMin(root.right);
          root.val = minNode.val;
          root.right = delete(root.right, root.val);
      }
      return root;
  }
  private TreeNode findMin(TreeNode node) {
      while (node.left != null) {
          node = node.left;
      }
      return node;
  }

• Time Complexity: O(n) (worst case for unbalanced tree), O(log n) (average case for balanced tree)
• Space Complexity: O(n) (worst case for unbalanced tree), O(log n) (average case for balanced tree)

Tree Traversal Techniques

1. In-Order Traversal (Left, Root, Right)

• Example:

  public void inOrder(TreeNode root) {
      if (root != null) {
          inOrder(root.left);
          System.out.println(root.val);
          inOrder(root.right);
      }
  }

• Time Complexity: O(n)
• Space Complexity: O(n) (worst case for unbalanced tree), O(log n) (average case for balanced tree)

2. Pre-Order Traversal (Root, Left, Right)

• Example:

  public void preOrder(TreeNode root) {
      if (root != null) {
          System.out.println(root.val);
          preOrder(root.left);
          preOrder(root.right);
      }
  }

• Time Complexity: O(n)
• Space Complexity: O(n) (worst case for unbalanced tree), O(log n) (average case for balanced tree)

3. Post-Order Traversal (Left, Right, Root)

• Example:

  public void postOrder(TreeNode root) {
      if (root != null) {
          postOrder(root.left);
          postOrder(root.right);
          System.out.println(root.val);
      }
  }

• Time Complexity: O(n)
• Space Complexity: O(n) (worst case for unbalanced tree), O(log n) (average case for balanced tree)

4. Level-Order Traversal (BFS)

• Example:

  public void levelOrder(TreeNode root) {
      if (root == null) {
          return;
      }
      Queue<TreeNode> queue = new LinkedList<>();
      queue.add(root);
      while (!queue.isEmpty()) {
          TreeNode node = queue.poll();
          System.out.println(node.val);
          if (node.left != null) {
              queue.add(node.left);
          }
          if (node.right != null) {
              queue.add(node.right);
          }
      }
  }

• Time Complexity: O(n)
• Space Complexity: O(n)

Common Leetcode Patterns

1. Tree Traversal

• Used for problems like in-order traversal, pre-order traversal, post-order traversal, etc.
• Related Questions:
  • Binary Tree Inorder Traversal
  • Binary Tree Preorder Traversal
  • Binary Tree Postorder Traversal

2. Path Sum

• Used for problems like path sum, maximum path sum, etc.
• Related Questions:
  • Path Sum
  • Path Sum II
  • Binary Tree Maximum Path Sum

3. Tree Depth and Height

• Used for problems like maximum depth of binary tree, minimum depth of binary tree, etc.
• Related Questions:
  • Maximum Depth of Binary Tree
  • Minimum Depth of Binary Tree
  • Balanced Binary Tree

4. Tree Symmetry

• Used for problems like symmetric tree, invert binary tree, etc.
• Related Questions:
  • Symmetric Tree
  • Invert Binary Tree
  • Same Tree

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Insertion	O(n) (worst)	O(n) (worst)
Search	O(n) (worst)	O(n) (worst)
Deletion	O(n) (worst)	O(n) (worst)
In-Order Traversal	O(n)	O(n) (worst)
Pre-Order Traversal	O(n)	O(n) (worst)
Post-Order Traversal	O(n)	O(n) (worst)
Level-Order Traversal	O(n)	O(n)

Related Leetcode Questions

Easy

1. Maximum Depth of Binary Tree
2. Symmetric Tree
3. Path Sum

Medium

1. Binary Tree Inorder Traversal
2. Binary Tree Level Order Traversal
3. Binary Tree Maximum Path Sum

Hard

1. Serialize and Deserialize Binary Tree
2. Binary Tree Cameras
3. Recover Binary Search Tree