Trees - 3 - Applications
Binary Search Tree
For a vertex with value $X$:
- Left child has value $\leq X$.
- Right child has value $> X$.
graph TD
60 --- 40
60 --- 90
40 --- 20
40 --- 50
20 --- 10
20 --- 30
90 --- 80
90 --- 110
80 --- 70
110 --- 100
110 --- 120
To search for a number go left if you want to go smaller and right if you want to go bigger.
In-order traversal gives the tree in ascending order.
Expression Tree
This tree represents a mathematical expression.
For the following expression:
\[(2+5*4)\times3\]In post-fix:
\[2\ 5\ 4 \times+\ 3\ \times\]graph TD
*1[*] --- +
*1 --- 3((3))
+ --- 2((2))
+ --- *2[*]
*2 --- 5((5))
*2 --- 4((4))
Post-order traversal will give the post-fix representation.