Binary Trees

Binary Trees in Java

Binary trees are a fundamental data structure in Java and are widely used in Leetcode problems. A binary tree is a tree data structure where each node has at most two children, referred to as the left child and the right child.

Table of Contents

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

Binary Tree Basics

• Definition: A binary tree is a tree data structure where each node has at most two children, referred to as the left child and the right child.
• 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 child is less than the parent node, and the right child is greater than the parent node (in a Binary Search Tree).
  • Can be traversed in various ways (in-order, pre-order, post-order, level-order).

Common Binary Tree 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