📖
Coding problems
  • Overview
  • Second time
  • Third time
  • 2 sum
    • 2 sum?
    • 2 Sum All Pair I
    • 2 Sum All Pair II
    • 3 Sum
  • Array
    • Smallest and Largest
    • Largest and second largest
    • Longest Palindromic Substring
  • BFS
    • Array Hopper IV
    • Deep copy graph(possible loops)
    • Kth Smallest With Only 3, 5, 7 As Factors
    • Word Ladder
  • Binary Search
    • Closest in Sorted Array
    • Smallest Element that is larger than target
    • Search in unknown size array
  • Bit Operations
    • Basic Operations
    • Power of two?
    • Different bits
    • Reverse all bits of a number
    • Unique String
  • Deque
    • Deque with 3 stacks
    • Largest Rectangle in histogram
  • DFS Permutations
    • All subsets I
    • All subsets size k
    • Combinations For Telephone Pad I
    • Subsets of all permuations
    • Generate N valid parentheses I
    • Generate N valid parentheses II
    • Generate N valid parentheses III
    • Combinations of Coin
    • All Permutation String
    • All Permutations II
    • Telephone Combinations
  • Dynamic Programming
    • Array Hopper I
    • Array Hopper II
    • Array Hopper III
    • Cut Rope
    • Dictionary Word 1
    • Dictionary Word II
    • Eat Pizza
    • Largest Cross of Ones
    • Largest Square Surrounded By One
    • Largest X of 1s
    • Largest Square of Matches
    • Largest Submatrix Sum
    • Longest Ascending Subsequence I & II
    • Longest Common Sequence between two strings
    • Most with positive slope
    • Palindrome Partition
    • Edit Distance
    • Square of ones
    • Wild card matching
    • Wood Cutting
    • 188. Best Time to Buy and Sell Stock IV
  • Graph Search
    • Kth closest to <0, 0, 0>
    • Largest Product of Length
  • HashTable
    • Top K frequent words
    • Bipartite
  • Heap
  • LinkedList
    • Reverse
    • Merge Sort Linked List
    • Re-Order LinkedList
  • Slow fast pointers
    • Remove duplicate elements in array
  • Problem Solving
    • Water Level I
    • Largest rectangle in histogram
    • Range Addition II
  • Recursion
    • ReverseTree
    • NQueen
    • NQueen optimized
    • Spiral Order Print I
    • Spiral Order Print II
    • String Abbreviation Matching
  • Sliding Window
    • Longest subarray contains only 1s
    • Longest Substring Without Repeating Characters
    • Maximum Number within Window
  • Sorts
    • QuickSort
  • String
    • All Anagrams
    • is substring of string
    • Reverse String
    • Reverse Words on sentence
    • Remove Chars from String in place
    • Right shift N characters
    • Remove Leading/duplicate/trailing spaces
    • Shuffle String
    • String Abbreviation Matching
  • Tree Traversal
    • Check balanced tree
    • Check if complete tree
    • Delete in binary tree
    • LCA of two tree nodes
    • Get Keys In Binary Search Tree In Given Range
    • Height of Tree
    • Symmetric Tree?
    • Tweaked Binary tree
    • Set left node count
    • Greatest difference Left and Right subtree count Node
    • Largest Number Smaller in BST
    • Closest Number in Binary Search Tree II
    • Max Path Sum From Leaf To Root
    • Maximum Path Sum Binary Tree I
    • Maximum Path Sum Binary Tree II
    • Maximum Path Sum Binary Tree III
    • Flatten Binary Tree to Linked List
    • Iterative Post-Order Traversal
  • Unsorted Array
    • Find missing number
Powered by GitBook
On this page

Was this helpful?

  1. Tree Traversal

Delete in binary tree

Delete the target key K in the given binary search tree if the binary search tree contains K. Return the root of the binary search tree.

Find your own way to delete the node from the binary search tree, after deletion the binary search tree's property should be maintained.

Assumptions

  • There are no duplicate keys in the binary search tree

    The smallest larger node is first candidate after deletion

Solution: Recursive traversal

case 1: node to delete no children //sever parent-> to node

case 2: no left child //re-attach right child to parent

case 3: no right child //re-attach left child to parent

case 4: both left and right child //A node from left or right tree will need to replace it //largest from right or smallest from left

/**
 * public class TreeNode {
 *   public int key;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int key) {
 *     this.key = key;
 *   }
 * }
 */
public class Solution {
  public TreeNode deleteTree(TreeNode root, int key) {
    if (root == null){
      return null;
    }
    if (key == root.key){ //if found
      if (root.left == null){
        return root.right;
      } else if (root.right == null){
        return root.left;
      } else if (root.right.left == null){
        root.right.left = root.left;
        return root.right;
      } else {
        TreeNode newRoot = deleteSmallest(root.right);
        newRoot.left = root.left;
        newRoot.right = root.right;
        return newRoot;
      }
    }
    if (key < root.key){
      root.left = deleteTree(root.left, key);
    } else if (key > root.key){
      root.right = deleteTree(root.right,key);
    }
    return root;
  }

  private TreeNode deleteSmallest(TreeNode root){
    while(root.left.left!= null){
      root = root.left;
    }
    TreeNode smallest = root.left;
    root.left = root.left.right;
    return smallest;
  }
}

TC:

PreviousCheck if complete treeNextLCA of two tree nodes

Last updated 4 years ago

Was this helpful?