Binary Search Tree

Description

The sorted version of a Binary Tree is called Binary Search Tree, which means:

1. For the root node, the value of all nodes in the left subtree < the value of the root node < the value of all nodes in the right subtree.
2. The left and right subtrees of any node are also binary search trees, i.e., they satisfy condition 1. as well.

Operations

Searching a Node

When we are looking for num, we declare a node cur, start from the binary tree's root node root, and loop to compare the size between the node value cur.val and num.

• If cur.val < num, it means the target node is in cur's right subtreep.
• If cur.val > num, it means the target node is in cur's left subtree.
• If cur.val = num, it means the target node is found, exit the loop, and return the node.

Inserting a Node

It works like this:

• Finding insertion position: Similar to the search operation, start from the root node, loop downwards according to the size relationship between the current node value and num, until the leaf node is passed (traversed to None), then exit the loop.
• Insert the node at this position: Initialize the node num and place it where None was.

Removing a Node

First, find the target node in the binary tree, then remove it. Similar to inserting a node, we need to ensure that after the removal operation is completed, the property of the binary search tree "left subtree < root node < right subtree" is still satisfied.

Vs Binary Tree