Trees

Question 1

What is a Tree?

Answer 1

structure consisting of one node called the root and zero or one or more subtrees

edges flow from the root

Question 2

Heap

Answer 2

complete binary tree which satisfies the heap ordering property

max-heap: every node is larger than its children
min-heap: every node is smaller than its children

insertion/deletion algorithm
deletion always happens at root

Question 3

Balanced Binary Tree

Answer 3

for every node, the height of each subtree does not differ by more than one

Question 4

Complete Binary Tree

Answer 4

every level of the tree is filled until the last level that is filled to the left with leaf nodes

Question 5

Binary Search Tree

Answer 5

left subtree of a node contains only nodes with smaller values

right subtree of a node contains only nodes with larger values

the left and right subtree each must also be a binary search tree

Question 6

Breadth First Traversal

Answer 6

algorithm for traversing or searching tree or graph data structures.

starts at the tree root (or some arbitrary node of a graph) and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level

Question 7

Depth First Traversal

Answer 7

algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking

Question 8

Types of Depth First Traversals

Answer 8

Preorder Traversal (root, left, right)
Inorder Traversal (left, root, right)
Postorder Traversal (left, right, root)