Binary Trees Flashcards
what’s the motivation behind developing trees
to access and search more efficiently than using linear data structures
definition of binary tree
- each node has at most 2 children
- children are labeled left and right
- left child precedees right child
what’s a full binary tree
each node must have either 0 or 2 children
what’s a complete binary tree
every level must be filled except for the last one, which is filled left to right
what’s a denegerate tree
a linked list
what’s BST
- a binary tree that has a certain order property where every node to the left branch of the current node must be smaller than the current node
- while every node to the right branch of the current node must be greater than the current node
what’s preorder traversal’s pseudocode
preorder(Node node)
if node is not null:
look at the data in node
recurse left
recurse right
what’s inorder traversal’s pesudocode
inorder(Node node)
if node is not null:
recurse left
look at the data in node
recurse right
what’s postorder traversal’s pesudocode
postorder(Node node)
if node is not null:
recurse left
recurse right
look at the data in node
what’s levelorder traversal’s pesudocode
levelorer():
Create Queue q
Add root to q
while q is not empty:
Node curr = q.dequeue()
if curr is not null:
q.enqueue(curr.left)
q.enqueue(curr.right)