Binary Trees

Question 1

what’s the motivation behind developing trees

Answer 1

to access and search more efficiently than using linear data structures

Question 2

definition of binary tree

Answer 2

1. each node has at most 2 children
2. children are labeled left and right
3. left child precedees right child

Question 3

what’s a full binary tree

Answer 3

each node must have either 0 or 2 children

Question 4

what’s a complete binary tree

Answer 4

every level must be filled except for the last one, which is filled left to right

Question 5

what’s a denegerate tree

Answer 5

a linked list

Question 6

what’s BST

Answer 6

• 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

Question 7

what’s preorder traversal’s pseudocode

Answer 7

preorder(Node node)
if node is not null:
look at the data in node
recurse left
recurse right

Question 8

what’s inorder traversal’s pesudocode

Answer 8

inorder(Node node)
if node is not null:
recurse left
look at the data in node
recurse right

Question 9

what’s postorder traversal’s pesudocode

Answer 9

postorder(Node node)
if node is not null:
recurse left
recurse right
look at the data in node

Question 10

what’s levelorder traversal’s pesudocode

Answer 10

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)