Trees for programming


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.


                                                                            A sample binary tree with seven nodes 

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. 

    1. 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.

      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 tree in above  Figure is actually a binary search tree.
www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community
 
Top Blogs