Data Structures: Question Set – 20
What is a tree data structure?
A tree is a hierarchical data structure consisting of nodes connected by edges. Each node has a parent node and zero or more child nodes, except for the root node, which has no parent. The root node is the topmost node in the tree, and all other nodes are descendants of the root node.
What is a binary tree?
A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
What is the height of a tree?
The height of a tree is the length of the longest path from the root node to any leaf node in the tree. It is the number of edges on the longest path from the root node to a leaf node.
What is a binary search tree?
A binary search tree is a binary tree in which the left subtree of a node contains only nodes with keys less than the node’s key, and the right subtree of a node contains only nodes with keys greater than the node’s key. This property allows for efficient searching, insertion, and deletion operations.
What is a balanced tree?
A balanced tree is a tree in which the heights of the subtrees of any node differ by at most one. This ensures that the height of the tree is logarithmic with respect to the number of nodes, which leads to efficient search, insertion, and deletion operations.
What is a traversal in a tree?
A traversal in a tree is the process of visiting each node in the tree exactly once. There are two main traversal algorithms: depth-first traversal and breadth-first traversal. In depth-first traversal, we first visit the left subtree, then the right subtree, and finally the root node. In breadth-first traversal, we visit all the nodes at each level of the tree, starting from the root node and moving down to the leaf nodes.
What is a leaf node in a tree?
A leaf node is a node in a tree that has no children. It is also referred to as a terminal node.
What is a parent node in a tree?
A parent node is a node in a tree that has one or more children. The root node has no parent.
What is a subtree in a tree?
A subtree is a portion of a tree that can be considered as a separate tree. It consists of a node and all its descendants, including the node itself.
What is a depth of a node in a tree?
The depth of a node in a tree is the length of the path from the root node to the node. The root node has a depth of 0.