Given a binary tree, write a function that prints all of the paths from the root node to the leaf nodes. What is the functions run time and space requirement.

Question

Traverse the tree, when you get to a leaf, print it · Accepted Answer

Traverse the tree, when you get to a leaf, print it. 


in this solution I am adding it  to a list, so I can test it

public class Tree
{
       Node Head;

        List m_paths;
        public List PathsToLeafs()
        {
            // not thread safe
            m_paths = new List();

            Path(Head, string.Empty);
            return m_paths;
        }

        public void Path(Node n, string p)
        {
            if (n == null)
            {
                return;
            }

            // add a separator if it's not the first node in the path
            p += (string.IsNullOrEmpty(p) ? string.Empty : " ") +
                       n.Value.ToString();
            if (n.Left == null && n.Right == null)
            {
                //leaf, add the path
                m_paths.Add(p);
                return;
            }
            Path(n.Left, p);
            Path(n.Right, p);
        }

       public InsertValue (int v) {
              // some code implemented here to add the node as a BST
        }

     public class Node
    {
        public int Value;
        public Node Left;
        public Node Right;
    }
}

The test class would be

using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace AlgorithmsTests
{
    [TestClass]
    public class TreeTests
    {
        [TestMethod]
        public void PrintAllPaths()
        {
           /* build the tree, i.e.

                 5
                /  \
               3    9
               \   / \
                4 6   11

          */
            BSTree tree = new BSTree();
            tree.InsertValue(5);
            tree.InsertValue(9);
            tree.InsertValue(6);
            tree.InsertValue(3);
            tree.InsertValue(4);
            tree.InsertValue(11);
        
            //print all paths
            List paths = tree.PathsToLeafs();
            Assert.AreEqual(3, paths.Count);
            Assert.IsTrue(paths.Contains("5 3 4"));
            Assert.IsTrue(paths.Contains("5 9 6"));
            Assert.IsTrue(paths.Contains("5 9 11"));
        }
    }
}

Soumasish Goswami · Answer

I've used a stack, the method is fairly intuitive.

public void printPath(Node root){
        Deque stack = new ArrayDeque();
        printPath(root, stack);

    }

    public void printPath(Node root, Deque stack){

        if(root == null) return;

        stack.offerFirst(root);
        printPath(root.left, stack);
        printPath(root.right, stack);
        if(root.left == null && root.right == null){
            Iterator itr = stack.descendingIterator();
            while(itr.hasNext()){
                Node p = (Node) itr.next();
                System.out.print(p.data + " ");
            }
            System.out.println();
        }
        stack.poll();


    }

Meta

Meta Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches