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.

[showads ad=inside_post]

class Path
{
private:
	std::vector<node *> elementList;
public:	
	void addElement(node * var)
	{
		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];
					pathObj.addElement(pRoot);
					listOfPaths.push_back(pathObj);
				}
			}
			Path pathObj;
			pathObj.addElement(pParent);
			pathObj.addElement(pRoot);
			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();
}