# Finding paths in a Binary Tree

Many times we need to search for some specific paths in a binary tree from top to bottom. Lets design a code to find out all paths in a binary tee.

For above binary tree, top to bottom paths are as follows,

5 —> 3

3 —> 1

3 —> 4

5 —> 10

10 —> 8

10 —> 11

5 —> 3 —-> 1

5 —> 3 —-> 4

5 —> 3 —-> 1

5 —> 10 —-> 8

5 —> 10 —-> 11

Technique:

Do the pre order traversal and while visiting each node,

• Create a path of between its parent and itself. Then insert this path in a path list.
• Then search paths in complete list, if any path’s last node matches with its parent then create a copy of that path and insert visiting node in it. Then add this new path to the path list.

How to define Path : A path contains a list of nodes.

```class Path
{
private:
std::vector<node *> elementList;
public:
{
elementList.push_back(var);
}
bool matchLast(node *  var)
{
if(elementList.size() == 0)
return false;
else
return (elementList[elementList.size() - 1] == var);
}
void print()
{
for(int i = 0; i < elementList.size() ; i++)
{
std::cout<<elementList[i]->value;
if(i < elementList.size() - 1 )
std::cout<<"--->";
}
std::cout<<"\n";
}
};
```

Class to generate paths,

```class BinaryTreePathFinder
{
std::vector<Path> listOfPaths;

public:
void inOrderTraverse(node * pRoot, node * pParent)
{
if(pRoot == NULL)
return;
if(pParent)
{
for(int i = 0; i < listOfPaths.size() ; i++)
{
if(listOfPaths[i].matchLast(pParent) )
{
Path pathObj = 	listOfPaths[i];
listOfPaths.push_back(pathObj);
}
}
Path pathObj;
listOfPaths.push_back(pathObj);
}
inOrderTraverse(pRoot->pLeft, pRoot);
inOrderTraverse(pRoot->pRight, pRoot);
}
std::vector<Path> getPaths(node * pRoot)
{
inOrderTraverse(pRoot, NULL);
return listOfPaths;
}

};
```

Usage Details,

```node * pRoot = createTree();
BinaryTreePathFinder pathFinderObj;
std::vector<Path> pathList = pathFinderObj.getPaths(pRoot);
for(int i = 0; i < pathList.size() ; i++)
{
pathList[i].print();
}
```

### 1 thought on “Finding paths in a Binary Tree”

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top