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

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