Binary Trees Flashcards
1
Q
What is a full binary tree?
A
A binary tree where every node has 0 or 2 children
AKA: all nodes except leaf nodes have two children
2
Q
What is a complete binary tree?
A
A binary tree where all levels are completely filled except possibly the last and the last level has all nodes as left as possible
3
Q
What is a perfect binary tree?
A
A binary tree in which all the parent ndoes have two children and all the leaf nodes are at the same level
4
Q
What is a balanced binary tree?
A
If the height of the tree is O(logN) where N is the number of nodes.
5
Q
What is the time complexity of searching a binary tree
A
O(H) where H is the height of the tree
6
Q
What is the time complexity of searching a balanced binary tree
A
O(logN), which is also the height of a balanced binary tree
