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.

BST
Binary Search Tree

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 to generate paths,

Usage Details,

Join LinkedIn Group of Python Professional Developers who wish to expand their network and share ideas.

You can also follow us On Twitter :

Click Here to Subscribe for more Articles / Tutorials like this.