Home » Algorithm » Binary Tree » Datastructure » Interviews » Print path from root to a given node in a binary tree

Print path from root to a given node in a binary tree

in , , , - on 11:05:00 - No comments

Print path from root to a given node in a binary tree.

Given a Binary tree and a Key, Print a path from root to a key node.
Note: Given tree is Binary Tree and not Binary Search Tree.

Lets see sample input and output for better understanding:
Print path from root to given node in binary tree
Print path from root to given node in binary tree

Algorithm 

From Root to Key:
Step 1. 
Do in-order traversal and check if the node is matching with the key?
If Yes, no need to further check further nodes and return true as indication that we found the node.
If No, collect the node as this node may be part of path from root to Key.

Step 2:
When the recursive function reverse back, if the result that is returned from recursive call is true either on left or right sub-tree, then current node will remain part of the path or else remove it from the path which we added initially assuming it may became part of the path.

From Key to Root:
Step 1:
Repeat the same step as above, but instead of adding the nodes in the path initially we will add it later when recursive call returns, so that node that are part of path is added in Reversed order.

Java Program to Print path from root to a given node AND
Path from Matching Node to Root Path in a binary tree.
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
package com.javabypatel.binarytree;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 
/*
  Input: key = 5
 
             1
           /   \
         2      3
        / \    / \
       4  5   6   7
 
    Output:
        From root to key: 1 -> 2 -> 5
        From key to root: 5 -> 2-> 1
 
  Input: key = 1
 
             1
           /   \
         2      3
        / \    / \
       4  5   6   7
 
    Output:
        From root to key: 1
        From key to root: 1
 
  Input: key = 4
 
             1
           /   \
         2      3
        / \    / \
       4  5   6   7
 
    Output:
        From root to key: 1 -> 2 -> 4
        From key to root: 4 -> 2 -> 1
 
 */
public class PrintPathFromRoot {
    private Node rootNode;
 
    public static void main(String[] args) {
        new PrintPathFromRoot();
    }
 
    public PrintPathFromRoot() {
        addNodeInBinaryTree(rootNode, 1);
        addNodeInBinaryTree(rootNode, 2);
        addNodeInBinaryTree(rootNode, 3);
        addNodeInBinaryTree(rootNode, 4);
        addNodeInBinaryTree(rootNode, 5);
        addNodeInBinaryTree(rootNode, 6);
        addNodeInBinaryTree(rootNode, 7);
 
        int key = 5;
 
        Result res = getPathFromRoot(rootNode, key, new Result("", false));
 
        System.out.println("Approach 1 result:");
        if (res.isResult()) {
            System.out.println(res.getPath());
        } else {
            System.out.println("No Path found");
        }
 
        List<Integer> path = new ArrayList<>();
        getPathFromRoot(rootNode, key, path);
        System.out.println("\nApproach 2 result:");
        if (path.size() > 0) {
            for (Integer i : path) {
                System.out.print(i + " ");
            }
        } else {
            System.out.println("No Path found");
        }
 
        path = new ArrayList<>();
        getPathFromRoot(rootNode, key, path);
        System.out.println("\nApproach 3 result:");
        if (path.size() > 0) {
            for (Integer i : path) {
                System.out.print(i + " ");
            }
        } else {
            System.out.println("No Path found");
        }
 
        path = new ArrayList<>();
        getPathFromRootReverse(rootNode, key, path);
        System.out.println("\nApproach 4 result:");
        if (path.size() > 0) {
            for (Integer i : path) {
                System.out.print(i + " ");
            }
        } else {
            System.out.println("No Path found");
        }
    }
 
    private Result getPathFromRoot(Node rootNode, int key, Result result) {
        if (rootNode == null) {
            return result;
        }
 
        if (rootNode.getData() == key) {
            return new Result(result.getPath() + " " + rootNode.getData(), true);
        }
 
        Result r = new Result(result.getPath() + " " + rootNode.getData(), false);
 
        Result onLeft = getPathFromRoot(rootNode.getLeft(), key, r);
        if (onLeft.isResult()) {
            return onLeft;
        }
        Result onRight = getPathFromRoot(rootNode.getRight(), key, r);
        if (onRight.isResult()) {
            return onRight;
        }
 
        return onLeft.isResult() ? onLeft : onRight;
    }
 
    private boolean getPathFromRoot(Node rootNode, int key, List<Integer> path) {
        if (rootNode == null) {
            return false;
        }
 
        path.add(rootNode.getData());
 
        if (rootNode.getData() == key) {
            return true;
        }
 
        boolean onLeft = getPathFromRoot(rootNode.getLeft(), key, path);
        if (onLeft) {
            return onLeft;
        }
        boolean onRight = getPathFromRoot(rootNode.getRight(), key, path);
        if (onRight) {
            return onRight;
        }
 
        path.remove(path.size() - 1);
        return false;
    }
 
    private boolean getPathFromRootReverse(Node rootNode, int key, List<Integer> path) {
        if (rootNode == null) {
            return false;
        }
 
        if (rootNode.getData() == key) {
            path.add(rootNode.getData());
            return true;
        }
 
        boolean onLeft = getPathFromRootReverse(rootNode.getLeft(), key, path);
        boolean onRight = getPathFromRootReverse(rootNode.getRight(), key, path);
 
        if (onLeft || onRight){
            path.add(rootNode.getData());
        }
 
        return onLeft || onRight;
    }
 
    //Iterative way of adding new Node in Binary Tree.
    private void addNodeInBinaryTree(Node rootNode, int data) {
 
        if (rootNode == null) {
            // No Nodes are Present, create one and assign it to rootNode
            this.rootNode = new Node(data);
 
        } else {
            //Nodes present, So checking vacant position for adding new Node in sequential fashion
            //Start scanning all Levels (level by level) of a tree one by one until we found a node whose either left or right node is null.
            //For each and every node, we need to check whether Left and Right Node exist?
            //If exist, then that node is not useful for adding new node but we need to store left and right node of that node for later processing
            //that is why it is stored in Queue for sequential placement.
            //If not exist, then we found a node, where new node will be placed but not sure on left or right, so check which side is null and place new node there.
 
            Queue<Node> q = new LinkedList<Node>();
            q.add(rootNode);
            while (!q.isEmpty()) {
                Node node = q.poll();
 
                if (node.getLeft() != null && node.getRight() != null) {
                    q.add(node.getLeft());
                    q.add(node.getRight());
                } else {
                    if (node.getLeft() == null) {
                        node.setLeft(new Node(data));
                    } else {
                        node.setRight(new Node(data));
                    }
                    break;
                }
            }
        }
    }
 
    private void printTreeLevelOrder(Node rootNode) {
        if (rootNode == null)
            return;
 
        Queue<Node> q = new LinkedList<Node>();
        q.add(rootNode);
        q.add(null);
 
        while (!q.isEmpty()) {
            Node node = q.poll();
 
            if (node == null) {
                if (q.peek() != null) {
                    System.out.println();
                    q.add(null);
                    continue;
                } else {
                    break;
                }
            }
 
            System.out.print(node.getData() + " ");
 
            if (node.getLeft() != null)
                q.add(node.getLeft());
 
            if (node.getRight() != null)
                q.add(node.getRight());
        }
    }
}
 
class Result {
    private String path;
    private boolean result;
 
    public Result(String path, boolean result) {
        this.path = path;
        this.result = result;
    }
 
    public String getPath() {
        return path;
    }
 
    public void setPath(String path) {
        this.path = path;
    }
 
    public boolean isResult() {
        return result;
    }
 
    public void setResult(boolean result) {
        this.result = result;
    }
}

Output:

Approach 1 result:
1 2 5
Approach 2 result:
1 2 5
Approach 3 result:
1 2 5
Approach 4 result:
5 2 1
Categories: , , ,