Data Structures: Question Set – 21
What is a binary tree?
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.
What is the difference between a binary tree and 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. A binary tree does not have any specific ordering of nodes.
What is a complete binary tree?
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
What is a full binary tree?
A full binary tree is a binary tree in which every node has either zero or two children.
What is a perfect binary tree?
A perfect binary tree is a binary tree in which all the internal nodes have two children and all the leaf nodes are at the same level.
What is the difference between preorder, inorder, and postorder traversal?
Preorder traversal visits the root node first, then recursively visits the left subtree and then the right subtree. Inorder traversal visits the left subtree first, then the root node, and then the right subtree. Postorder traversal visits the left subtree first, then the right subtree, and then the root node.
What is a binary tree height-balancing technique?
Height-balancing is a technique used to balance a binary tree so that the height of the tree remains small. The two most popular height-balancing techniques are the AVL tree and the Red-Black tree.
What is a binary tree level-order traversal?
Level-order traversal, also known as breadth-first traversal, visits all the nodes of a binary tree level by level, from left to right.
What is a binary tree leaf node?
A leaf node, also called a terminal node, is a node in a binary tree that does not have any children.
What is a binary tree path?
A binary tree path is a sequence of nodes that are connected by edges in a binary tree. The path starts at the root node and ends at a leaf node.