Trees BSEMC

What is a binary tree?

• A binary tree is a tree where each node can have any number of children.

• A binary tree is a type of graph that contains cycles.

• A binary tree is a linear data structure with only one child per node.

• A binary tree is a tree data structure where each node has at most two children.

Define a full binary tree.

• A full binary tree is a tree with only leaf nodes.

• A full binary tree is a tree where every node has at least one child.

• A full binary tree is a tree where every node has 0 or 2 children.

• A full binary tree is a tree where every node has 1 or 3 children.

What is the maximum number of nodes in a binary tree of height h?

• 2^(h+1) - 1

• h!

• h^2

• 2^h

Explain the difference between a binary tree and a binary search tree.

• A binary tree is always balanced, whereas a binary search tree can be unbalanced.

• A binary tree is used for sorting data, while a binary search tree is not suitable for sorting.

• A binary tree can have any number of children per node, while a binary search tree can only have two.

• A binary tree has no specific ordering of nodes, while a binary search tree has a defined order based on node values.

What is the purpose of tree traversal?

• To visualize the structure of a tree

• The purpose of tree traversal is to access and manipulate each node in a tree structure.

• To delete nodes from a tree structure

• To create a new tree from existing nodes

List the three main types of tree traversal algorithms.

• Random-order, Circular-order, Spiral-order

• Level-order, Depth-first, Breadth-first

• Pre-order, In-order, Post-order

• Top-down, Bottom-up, Side-order

Describe the in-order traversal method.

• In-order traversal visits nodes in the order: left, root, right.

• In-order traversal visits nodes in the order: left, right, root.

• In-order traversal visits nodes in the order: right, root, left.

• In-order traversal visits nodes in the order: root, left, right.

How does pre-order traversal differ from post-order traversal?

• Pre-order traversal processes the root after its children, while post-order traversal processes the root before its children.

• Both pre-order and post-order traversals process the root at the same time.

• Pre-order traversal only processes leaf nodes, while post-order traversal processes all nodes.

• Pre-order traversal processes the root before its children, while post-order traversal processes the root after its children.

What is the time complexity of in-order traversal for a binary tree?

• O(n^2)

• O(log n)

• O(n)

• O(1)

Explain how breadth-first traversal works.

• Breadth-first traversal explores all neighbors at the present depth before moving to the next level.

• Breadth-first traversal only visits the starting node.

• Breadth-first traversal goes deep into one branch before exploring others.

• Breadth-first traversal randomly selects nodes to visit.