What will I be covering today?

Well, I will be covering a few common LeetCode questions in a few posts, one of them being, finding the lowest common ancestor/value of a Binary Search Tree, or BST for short.

What exactly is a Binary Search Tree and why do we learn about it?

Simply put, a Binary Search Tree is a node-based binary tree data structure that has the following properties:

• The left subtree of the nodes/values that are lesser than the root value of the original node.
• The right subtree has nodes/values that are more than the root value of the original node.
• The left/right subtree must also be a binary search tree.

Terminologies of a Binary Tree

Depth of a Binary Tree – The number of edges from a node in the tree to the root node.

Height of a Binary Tree – The number of edges from the deepest node in the tree to the root node.

What are nodes? And what are the various types of nodes?

Nodes are the building blocks of any data structure. They mostly contain some data and are linked to the next/previous nodes.

Root Node - It is the topmost node in a binary tree, and every binary tree can only have one root node. (top layer)

Parent Nodes - They are nodes that are on a level below the root node, they also have other nodes below them. (top-middle layer)

Child nodes - These are the nodes that are below the parent node, it can be both parent/child depending on the node above/below it. (middle layer)

Internal Node – A node that has at least one child node below it. (middle-bottom layer)

Leaf Node – A node with no other nodes below it. (bottom layer)

How to find the lowest common ancestor of a Binary Search Tree?

This is my solution on LeetCode (Python 3), the comments explain what I have done:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        #get the smallest value in p and q, by using the min/minimum function
        small = min(p.val, q.val)
        #get the biggest value in p and q
        biggest = max(p.val, q.val)
        #while the root is True/not empty
        while root:
            #if the value of the root is bigger than the biggest value or p/q, then put the value on the left of the root node
            if root.val > biggest:
                root = root.left
            #if the root value is smaller than the smallest value of p and q, then place the value on the right side of the root node
            elif root.val < small:
                root = root.right
            #if the root value is in the middle of the biggest and smallest, then return the root node
            else:
                return root
        #other than that, return nothing
        return None

Conclusion

A Binary Search Tree is useful for finding certain elements in a data structure by using a few simple functions in Python 3, like min, max, val (value of the variable), root.right (the right subtree that branches out from the root node), and root.left (left subtree that branches out from the root node).