(b) Binary Search Tree

What is a graph?

an a data structure/tree made up of nodes connected via edges/arc representing RS between diff nodes

What is a tree?

a dynamic data structure - a graph with no cycles

What are the three types of trees?

• binary tree

• binary search tree

• rooted tree

What is the difference between a binary tree and binary search tree?

• binary tree = rooted tree where each node can have max. 2 child nodes

• binary search tree = binary tree where if child node is less than root node, it is put to the left, if child node is more than root node, it is put to the right

What do we call nodes at the bottom of the tree?

leaf nodes

What are the uses of rooted trees?

• storing + managing file & folder structures

• implementations of A* pathfinding algorithm

• storing + manipulating hierarchical data

What are the maximum amount of child nodes a binary tree can have?

2

What are the two ways a binary tree can be implemented?

• using a dictionary

• using an array

How would these tree by implemented using a dictionary?

How would these tree by implemented using an array?

What are the uses of a binary tree?

• database applications (efficient searching + sorting)

• wireless networking & router tables

• OS scheduling processes

How do you add an item to a binary tree?

How do you delete an item from a binary tree?

How do you search a binary tree for an item?

• check if root node is equal to search value - if so return found

• if value is less than root node take left subtree

• if value is greater than root node take right subtree

• repeat process w/ subtree

• until search value is found

• until no more branches can be travelled

How do you perform a depth-first (post-order) travels on a binary search tree?

• start at the root node - go all the way down the branch to the leaf node

• pushes visited nodes onto stack

• continues to backtrack until node is reach w/ univisited children - checks down that branch (backtracks to previous node & explore all those branches)

How do you perform a breadth-first (pre-order) travels on a binary search tree?