Tree search

A tree is model used to represent hierarchical data. In correspondence to natural trees, it has nodes, leaves and branches. A commonly mentioned tree is a binary tree, in which each node contains leads to two other nodes.

In the above example, each bubble represents a 'node'. The arrows pointing from one bubble to another bubble are called 'edges'. The topmost node ("computer hardware") with no edges leading to it is called the'root'. One or more nodes that immediately follow from a node is called a 'child'. Another important term is depth of a node defined as the length of the path from the root node to that node.

Binary trees are represented in programming languages using linked lists. For example, in C a tree grows from a node:

                                              struct  node {

                                                                 struct node* l;
                                                                 struct node* r; /*two pointers ,one pointing to node to the right and one to left ( both below the current node) */
                                                                 int d;
                                                                    };

A tree search starts at the root and explores nodes from there, looking for one particular node that satisfies the conditions mentioned in the problem. Unlike linear data structures, the elements can be traversed in many ways. There are many algorithms that use different order to traverse/pass through a node.

One such method is depth first search.

Depth first search: We start from the root and go as far as possible (deeper) along each branch before backtracking. In this example, if we were to find the node 7, the algorithm traces from node 1 -> node 8 -> node 6 -> node 10 ->node 6 (backtracks) -> node 7.

Recursive depth first search:

search(node):

 if (node==node searched){
               print(node);
                return success;
                      }

 else 
     for every child c of node {
             if search(c) is successful
                    return success;  }

 To keep track of the nodes visited ,a stack is used.

                 1)visit a node, then push all of the nodes to be visited into the stack. 

                  2)For the next node we simply pop a node from the stack and then push all the nodes connected to that one into the stack.

                  3)Repeat 1) and 2)  until the node has been found or all the nodes are visited.

Breadth first search( pseudo-code):

• Node- is a class of nodes in a tree,
• root - is a root node of a given tree,
• queue - is a queue implemented so it can store objects of Node class within it,
• enqueue(), dequeue() - functions of putting in, reading from, the queue,
• visit() - a function that does something we want with a given node(prints it, or changes data in it etc.),
• isEmpty() - a function that determines whether the queue is empty or not,

• left , right - left, right child of a given Node

• 1) Node* p = root;

• 2) if(p != NULL)
• 3)then
• 4) queue.enqueue(p);
• 5) while( ! queue.isEmpty() )
• 6) do
• 7) p = queue.dequeue();
• 8) p.visit();
• 9) if( p.left != NULL)
• 10) then queue.enqueue(p.left);
• 11) if( p.right != NULL)
• 12) then queue.enqueue(p.right);
• 13) end while;
• 14) end if;
• 15) end;