Binary Trees and Binary Search Trees | Notion

Binary Trees

Each node has at most two children (it can also have none or one)
- there may be an left child;
- there may be an right child.
A binary tree is eather:
- empty, or
- a node that has a left and right subtree

Terminology

Proper binary tree - each node has either two children or none (a leaf);
Full binary tree - a proper binary tree in which all leaves are at the same depth.
Questions

Traversals

Visiting each node in a specific order.

Traversal	Order of Visit	Description
Pre-order	Root → Left → Right	Visit the root first, then subtrees
In-order	Left → Root → Right	Visit left subtree, then root, then right
Post-order	Left → Right → Root	Visit both subtrees before the root

In-order Traversal :

Begin at the root.
Traverse the left subtree.
Visit (report) the current node.
Traverse the right subtree.

(always go back to the root of each node! -At every subtree repeat the same process recursively.)