January 2014 | cinterviews | interview questions | tutorials

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

Q.1 How do you find whether there is a loop in a linked list? For example, the list in Figure bellow contains a loop.

A list with a loop

This is a popular interview question. It can be solved with two pointers, which are initialized at the head of list. One pointer advances once at each step, and the other advances twice at each step. If the faster pointer meets the slower one again, there is a loop in the list. Otherwise, there is no loop if the faster one reaches the end of list.
The sample code in bellow is implemented based on this solution. The faster pointer is pFast, and the slower one is pSlow.

C++ Code to Check Whether a List Contains a Loop
```
bool HasLoop(ListNode* pHead) {
    if(pHead == NULL)
```
```
        return false;
```
```
    ListNode* pSlow = pHead->m_pNext;
    if(pSlow == NULL)
```
```
        return false;
```
```
    ListNode* pFast = pSlow->m_pNext;
    while(pFast != NULL && pSlow != NULL) {
```
```
        if(pFast == pSlow)
            return true;
```
```
        pSlow = pSlow->m_pNext;
```
```
        pFast = pFast->m_pNext;
        if(pFast != NULL)
```
```
            pFast = pFast->m_pNext;
```
}
```
    return false;
}
```
Test Cases:
- There is a loop in a list (including cases where there are one/multiple nodes in a loop, or a loop contains all nodes in a list)
- There is not a loop in a list
- The input node of the list head is NULL
  
  Q.
  
  If there is a loop in a linked list, how do you get the entry node of the loop? The entry node is the first node in the loop from the head of a list. For instance, the entry node of the loop in the list of Figure bellow is the node with value 3.
  
  A list with a loop
  
  we can also solve this problem with two pointer.Two pointers P1 and P2 are initialized to point to the head of a list. If there are n nodes in the loop, the first pointer move forward n steps, and then two pointers move together with same speed. When the second pointer reaches the entry node of the loop, the first one travels around the loop and returns back to the entry node.
  
  Let’s take the list in Figure above as an example. P1 and P2 are first initialized to point to the head node of the list (Figure (a)). There are four nodes in the loop of the list, so P1 moves four steps ahead and reaches the node with value 5 (Figure (b)). Then these two pointers move two steps, and they meet at the node with value 3, which is the entry node of the loop, as shown in Figure (c).
  
  Process to find the entry node of a loop in a list. (a) Pointers P1 and P2 are initialized at the head of list. (b) The pointer P1 moves four steps ahead since there are four nodes in the loop. (c) Both P1 and P2 move ahead till they meet at the entry node of the loop.
  The only problem is how to figure out the number of nodes inside a loop. Let’s go back to the solution of the previous question. Two pointers are employed, and the faster one meets the slower one if there is a loop. The meeting node should be inside the loop. Therefore, we can move forward from the meeting node and count nodes in the loop until we arrive at the meeting node again.
  The function Meeting Node in bellow code finds the meeting node of two pointers if there is a loop in a list, which is a minor modification of the previous HasLoop.
  C++ Code to Get a Meeting Node in a Loop
  
  ListNode* MeetingNode(ListNode* pHead) { if(pHead == NULL)
  return NULL;
  
  ListNode* pSlow = pHead->m_pNext; if(pSlow == NULL)
  return NULL;
  
  ListNode* pFast = pSlow->m_pNext; while(pFast != NULL && pSlow != NULL) {
  
  if(pFast == pSlow) return pFast;
  
  pSlow = pSlow->m_pNext; pFast = pFast->m_pNext;
  
  if(pFast != NULL) pFast = pFast->m_pNext;
  
  }
  
  return NULL; }
  The function MeetingNode returns a node in the loop when there is a loop in the list. Otherwise, it returns NULL.
  After finding the meeting node, it counts nodes in a loop of a list, as well as finding the entry node of the loop with the sample code, as shown inbellow code.
  C++ Code to Get a Meeting Node in a Loop
  
  ListNode* EntryNodeOfLoop(ListNode* pHead) { ListNode* meetingNode = MeetingNode(pHead); if(meetingNode == NULL)
  return NULL;
  
  // get the number of nodes in loop int nodesInLoop = 1; ListNode* pNode1 = meetingNode; while(pNode1->m_pNext != meetingNode) {
  
  pNode1 = pNode1->m_pNext;
  
  ++nodesInLoop; }
  
  // move pNode1 pNode1 = pHead; for(int i = 0; i < nodesInLoop; ++i)
  
  pNode1 = pNode1->m_pNext;
  
  // move pNode1 and pNode2 ListNode* pNode2 = pHead; while(pNode1 != pNode2){
  
  pNode1 = pNode1->m_pNext;
  
  pNode2 = pNode2->m_pNext; }
  
  return pNode1; }
  Test Cases:
  
  There is a loop in a list (including cases where there are one/multiple nodes in a loop, or a loop contains all nodes in a list)
  
  There is not a loop in a list
  
  The input node of the list head is NULL

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

Trees for programming

Examples for Loop in List

Q.

Subscribe Cinterviews.com

Topics