Recursion and Binary Trees

Question 1

means “defining a problem in terms of itself”.

Answer 1

RECURSION

Question 2

It is commonly used in mathematics, where there are many examples of expressions written in terms of themselves.

Answer 2

RECURSION

Question 3

what is Recursive Algorithm

Answer 3

A recursive algorithm calls itself with smaller input values and obtains the results by simply performing the operations on these smaller values. If a problem can be solved using smaller versions of the problem, and the smaller versions reduce to solve another problem, then one can utilized a recursive algorithm to solve that problem.

Question 4

Designing Recursive Algorithms

Answer 4

Initialize the algorithm.

Check to see whether the current value(s) being processed match the base case. If so, process and return the value.

Redefine the answer in terms of a smaller or simpler sub-problem or sub-problems.

Run the algorithm on the sub-problem.

Combine the results in the formulation of the answer.

Question 5

Limitations of Recursive Approach:

Answer 5

Recursive solutions may involve extensive overhead because they use function calls.

Each time you call a function you use up some of your memory allocation may be in stack or heap. If there are large number of recursive calls – then you may run out of memory.

Question 6

A binary tree is a a collection of ___ that consists of the _______ and other subsets to the __________, which are called the ___ and ___________

Answer 6

A binary tree is a a collection of nodes that consists of the root and other subsets to the root points, which are called the left and right subtrees.

Question 7

Every _______ node on a binary tree can have up to ______ (roots of the two subtrees); any more children and it becomes a general tree.

Answer 7

Every parent node on a binary tree can have up to two child nodes (roots of the two subtrees); any more children and it becomes a general tree.

Question 8

A node that has no children is called a

Answer 8

leaf node.

Question 9

Visit the root, traverse the left subtree and then traverse the right subtree

Answer 9

Preorder

Question 10

Traverse the left subtree (), traverse the right subtree () and then visit the root.

Answer 10

Postorder

Question 11

Traverse the left subtree, visit the root and the traverse the right subtree ().

Answer 11

in order

Question 12

We can construct a simple search tree if we add new nodes with value x on the tree using this strategy:

Answer 12

Every time x is less than the value in the node we move down to the left.
Every time x is greater than the value in the node we move down to the right.