Trees:
Trees are commonly used during our daily programming. In trees, all nodes except the root node have a parent node, and all nodes except leaves have one or more children nodes.
Interview questions about trees are usually not easy because there are many pointer operations on trees. If interviewers would like to examine candidates' capacity to handle complex pointer operations, they are likely to employ questions about trees.
Trees are commonly used during our daily programming. In trees, all nodes except the root node have a parent node, and all nodes except leaves have one or more children nodes.
Interview questions about trees are usually not easy because there are many pointer operations on trees. If interviewers would like to examine candidates' capacity to handle complex pointer operations, they are likely to employ questions about trees.
Both arrays and lists are linear data structures, so it is difficult to utilize them to organize a hierarchical
representation of objects. To overcome this limitation, a new data type named a tree was introduced,
which consists of a set of nodes and links among them.
Most trees referred to during interviews are binary trees, where every node has two children at most.
The most important operation on trees is traversal, which is to visit nodes in some order. The most
common traversal algorithms include the following:
-
Pre-order traversal: The root of a binary tree is visited first, then its left children,
and finally its right children. The pre-order traversal sequence of the binary tree in above
Figure is 10, 6, 4, 8, 14, 12, 16.
-
In-order traversal: Left children of a binary tree are visited first, then its root, and
finally its right children. The in-order traversal sequence of the binary tree in above
Figure is 4, 6, 8, 10, 12, 14, 16.
-
Post-order traversal: Left children of a binary tree are visited first, then its right
children, and finally its root. The post-order traversal sequence of the binary tree
in above Figure is 4, 8, 6, 12, 16, 14, 10.
-
Breadth-first traversal: Nodes in the first level are traversed, then nodes in the
second level, ..., and finally nodes in the bottom level. Nodes in the same level are
usually traversed from left to right. The breadth-first traversal sequence of the
binary tree in above Figure is 10, 6, 14, 4, 8, 12, 16.
-
The first three traversal algorithms in the preceding list can be implemented with both recursion
and iteration, and recursive implementations are more concise than iterative ones. Candidates should
be very familiar with these six implementations and be able to implement them with bug-free code in a
short period of time.
The tree in above Figure is actually a binary search tree.Usually, a queue is utilized for breadth-first traversal algorithms. There are also many interesting interview questions on this topic, which are discussed in the section Print Binary Trees Level by Level.
There are some special binary trees such as binary search trees. In a binary search tree, all nodes in the left subtree are not greater than the root node, and all nodes in the right subtree are not less than the root node. Binary search trees are closely related to the binary search algorithm, where it costs O(logn) time to find a value among n nodes.
-
The first three traversal algorithms in the preceding list can be implemented with both recursion
and iteration, and recursive implementations are more concise than iterative ones. Candidates should
be very familiar with these six implementations and be able to implement them with bug-free code in a
short period of time.
No comments:
Post a Comment