Trees

What are Trees?

樹結構

• Trees are Hierarchical data structure

• Node

• Child

• Parent

• Edge

• Leaf

• Subtree

• Every item in the tree is a node

• The node at the top of the tree is the root

• Every non-root node has one and only one parent

• A leaf node has no children

• A singleton tree has only one node: the root

Binary Search Trees

• Every node has 0, 1, or 2 children
• Children are referred to as left child and right child
• Can perform insertions, deletions and retrievals in $O(\log{n})$ time
• The left child always has a smaller value than its parent
• The right child always has a larger value than its parent

Binary Search Trees Implementation

Challenge 01

Challenge 01

Challenge 01