BCSC0006 Trees

In a ____, for any node 'n' every descendant node's value in the left subtree is less than n and in the right subtree is greater than n.

• Binary Tree

• Binary Search Tree

• AVL Tree

• Binary Heap Tree

The ____ of a Binary Search Tree starts by visiting the current node, then its left child node and then its right child node.

• Pre-Order Traversal

• In-Order Traversal

• Post-Order Traversal

• Linear Order Traversal

A ____ is a Binary Search Tree whose left and right subtree differ in height by at most 1 unit; and whose left and right subtrees are AVL trees.

• Red-Black Tree

• AVL Tree

• Binary Heap Tree

• Complete Binary Tree

For an AVL Tree, the ____ is the additional piece of information which indicates if the difference in height between the left and the right subtree is the same or not; which of the two subtrees has one unit larger height.

• Tree Factor

• Balance Factor

• Additional Factor

• Unit Factor

True statement about AVL Trees are

• It is a Binary Search Tree

• Left Node and Right Node differ in height by at most 1 unit

• Worst Case Complexity is O(log n)

• Worst Case Complexity is O(n)

A Binary Tree can have

• 2 children

• 1 child

• 0 child

• all of the above

Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without performing any rotations?

• just build the tree with the given input

• find the median of the set of elements given, make it as root and construct the tree

• use trial and error

• use dynamic programming to build the tree

Which of the following graph traversals closely imitates level order traversal of a binary tree?

• Depth First Search

• Breadth First Search

• Depth & Breadth First Search

• Binary Search

What is the time complexity of level order traversal?

• O(1)

• O(n)

• O(logn)

• O(nlogn)

Which of these are auto-balancing?

• AVL Trees

• Binary Trees

• Huffman Trees

• Expression Tree