Leetcode Day 16 - Binary Tree: Binary Search Tree Special Cases

Binary Tree

Link to note about binary tree

Diff	Problem	Python	Java
	530 Minimum Absolute Difference in BST	✅
	501 Find Mode in Binary Search Tree	✅
	236 Lowest Common Ancestor of a Binary Tree	✅

Minimum Absolute Difference in BST

Link to Leetcode question¹

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1

Input: root = [4,2,6,1,3]
Output: 1

Example 2

Input: root = [1,0,48,null,null,12,49]
Output: 1

Solution

A detailed explaination of solution can be found here².

Python

class Solution(object):
    def getMinimumDifference(self, root):
        minab = [float('inf')]
        que = []
        
        def inorder(node):
            if node is None:
                return

            inorder(node.left)

            if len(que) > 0:
                prv = que[-1] 
                minab[0] = min(minab[0], abs(node.val - prv))

            que.append(node.val)

            inorder(node.right)
        
        inorder(root)
        return minab[0] 

Similar Questions

Diff	Similar Questions	Python	Java
	532 K-diff Pairs in an Array3

Find Mode in Binary Search Tree

Link to Leetcode question⁴

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
• Both the left and right subtrees must also be binary search trees.

Example 1

Input: root = [1,null,2,2]
Output: [2]

Example 2

Input: root = [0]
Output: [0]

Solution

A detailed explaination of solution can be found here⁵.

Python

class Solution(object):
    def __init__(self):
        self.dict = {}
        self.ans=[]
        self.mx=-1
    def solve (self,root):
        if root is None: return
        self.dict[root.val] = self.dict.get(root.val, 0) + 1
        if self.dict[root.val]==self.mx:
            self.ans.append(root.val)
        elif self.dict[root.val]>self.mx:
            self.mx=self.dict[root.val]
            self.ans=[]
            self.ans.append(root.val)

        self.solve(root.left)
        self.solve(root.right)
    def findMode(self, root):
        
        self.solve(root)
        return self.ans

Lowest Common Ancestor of a Binary Tree

Link to Leetcode question⁶

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3

Input: root = [1,2], p = 1, q = 2
Output: 1

Solution

A detailed explaination of solution can be found here⁷.

Python

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        if root is None:
            return None
        
        if root == p or root == q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root
        
        return left if left else right

Similar Questions

Reference

1. Leetcode-530 Minimum Absolute Difference in BST: https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/. ↩︎

2. 代码随想录-二叉搜索树的最小绝对差: https://programmercarl.com/0530.二叉搜索树的最小绝对差.html. ↩︎

3. Leetcode-532 K-diff Pairs in an Array: https://leetcode.com/problems/k-diff-pairs-in-an-array/. ↩︎

4. Leetcode-501 Find Mode in Binary Search Tree: https://leetcode.com/problems/find-mode-in-binary-search-tree/description/. ↩︎

5. 代码随想录-二叉搜索树中的众数: https://programmercarl.com/0501.二叉搜索树中的众数.html. ↩︎

6. Leetcode-236 Lowest Common Ancestor of a Binary Tree: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/. ↩︎

7. 代码随想录-二叉树的最近公共祖先: https://programmercarl.com/0236.二叉树的最近公共祖先.html. ↩︎