Nodes with value, left and right
Each TreeNode stores its value and two links: left and right. From the root 50 hang two subtrees: 30 on the left and 70 on the right.
Each TreeNode stores its value and two links: left and right.
From the root 50 hang two subtrees: 30 on the left and 70 on the right.
Each TreeNode stores its value and two links: left and right. From the root 50 hang two subtrees: 30 on the left and 70 on the right.
The BST property: smaller values on the left (<) and larger values on the right (>).
That rule holds at every node: it turns every search into a decision.
The BST property: smaller values on the left (<) and larger values on the right (>). That rule holds at every node: it turns every search into a decision.
In main, search(35) starts at the root 50 and compares: 35 < 50.
By branching left toward 30, it discards the entire right subtree at once.
Nodes 70, 60 and 80 are never even visited: 35 cannot be there.
In main, search(35) starts at the root 50 and compares: 35 < 50. By branching left toward 30, it discards the entire right subtree at once. Nodes 70, 60 and 80 are never even visited: 35 cannot be there.
At node 30 it compares again: since 35 > 30, it branches right and discards 20.
It reaches 35 == 35: value found in O(log n) steps, proportional to the height.
At node 30 it compares again: since 35 > 30, it branches right and discards 20. It reaches 35 == 35: value found in O(log n) steps, proportional to the height.
But beware: if you insert values already sorted, the tree degenerates into a chain.
With no subtrees to discard, searching costs O(n) again just like a list.
But beware: if you insert values already sorted, the tree degenerates into a chain. With no subtrees to discard, searching costs O(n) again just like a list.
insert(25) descends by the same rule: 25 < 50 to 30, and 25 < 30 to 20.
Since 25 > 20, it follows the right link and hits null: the empty spot.
The base case creates new TreeNode(25); on return, node.right attaches it as a new leaf.
insert(25) descends by the same rule: 25 < 50 to 30, and 25 < 30 to 20. Since 25 > 20, it follows the right link and hits null: the empty spot. The base case creates new TreeNode(25); on return, node.right attaches it as a new leaf.
The preOrder, inOrder and postOrder traversals change when they visit the root.
Because inOrder visits left, root and right, it walks the values in ascending order.
The preOrder, inOrder and postOrder traversals change when they visit the root. Because inOrder visits left, root and right, it walks the values in ascending order.
BST property: smaller values on the left and larger on the right in every subtree.
When the tree is balanced, each step discards half the tree: O(log n).
And the inOrder traversal delivers all the values sorted without sorting anything.
BST property: smaller values on the left and larger on the right in every subtree. When the tree is balanced, each step discards half the tree: O(log n). And the inOrder traversal delivers all the values sorted without sorting anything.