Binary Trees Flashcards
What is a full binary tree?
A binary tree where every node has 0 or 2 children
AKA: all nodes except leaf nodes have two children
![](https://s3.amazonaws.com/brainscape-prod/system/cm/345/013/289/a_image_thumb.png?1620226014)
What is a complete binary tree?
A binary tree where all levels are completely filled except possibly the last and the last level has all nodes as left as possible
![](https://s3.amazonaws.com/brainscape-prod/system/cm/345/013/426/a_image_thumb.png?1620226055)
What is a perfect binary tree?
A binary tree in which all the parent ndoes have two children and all the leaf nodes are at the same level
![](https://s3.amazonaws.com/brainscape-prod/system/cm/345/013/840/a_image_thumb.png?1620226092)
What is a balanced binary tree?
If the height of the tree is O(logN) where N is the number of nodes.
What is the time complexity of searching a binary tree
O(H) where H is the height of the tree
What is the time complexity of searching a balanced binary tree
O(logN), which is also the height of a balanced binary tree