Google Interview Question Software Engineers
Country: United States
// ZoomBA
// Tree Node schema
def t_node : { v : 0 , l : left_node , r : right_node }
paths = list()
def find_paths( node , path ){
if ( empty(node) ){
paths.add ( path.split('/') )
return
}
if ( !empty( node.left ) ){
find_paths ( node.left , path + '/' + node.left.v )
}
if ( !empty( node.right ) ){
find_paths ( node.right , path + '/' + node.right.v )
}
}
// call this way
find_paths ( root, '/' + root.v )
Juste a simple DFS solution, saving the path in a list:
private List<Integer> path;
private List<String> result;
public List<String> nodeToLeafPaths(TreeNode root){
path = new LinkedList<>();
result = new LinkedList<>();
leafPath(root);
return result;
}
public void leafPath(TreeNode node){
if(node != null){
path.add(node.val);
if(node.left == null && node.right == null){
StringBuilder sb = new StringBuilder();
int i = 0;
for(Integer n : path){
sb.append(n);
if(i++ != path.size() - 1)
sb.append(“->”);
}
result.add(sb.toString());
}
leafPath(node.left);
leafPath(node.right);
path.remove(path.size() - 1);
}
}
import java.util.*;
public class RootToLeafPath {
public static void path(Node root,ArrayList<String> pathList,String builder){
if(root.left==null && root.right==null){
pathList.add(builder+root.data);
}else{
String s= root.data+"->";
if(root.left!=null){
path(root.left, pathList,builder+s);
}
if(root.right!=null){
path(root.right, pathList, builder+s );
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Insert obj=new Insert();
Node root=obj.getSampleRoot();
ArrayList<String> pathList=new ArrayList<>();
path(root, pathList, "");
for(String path:pathList){
System.out.println(path);
}
}
}
Iterative solution.
public ArrayList<String> getAllPaths(TreeNode<Integer> root){
if(root == null) return null;
Queue queue = new Queue();
queue.enqueue(root);
queue.enqueue(String.valueOf(root.getData()));
ArrayList<String> result = new ArrayList<>();
while(!queue.isEmpty()){
TreeNode<Integer> currNode = (TreeNode<Integer>) queue.dequeue();
String currPath = (String) queue.dequeue();
if(currNode.isLeaf()){
result.add(currPath);
continue;
}
if(currNode.getLeft() != null){
TreeNode<Integer> leftNode = currNode.getLeft();
queue.enqueue(leftNode);
currPath += " -> " + String.valueOf(leftNode.getData());
queue.enqueue(currPath);
}
if(currNode.getRight() != null){
TreeNode<Integer> rightNode = currNode.getRight();
queue.enqueue(rightNode);
currPath += " -> " + String.valueOf(rightNode.getData());
queue.enqueue(currPath);
}
}
return result;
}
public static void printStack(Stack<Integer> nodeData){
Iterator<Integer> it = nodeData.iterator();
System.out.println("Start Stack");
while(it.hasNext()){
int data = it.next();
System.out.println(data);
}
System.out.println("End Stack");
}
public static void printAllPath(TreeNode root, Stack<Integer> nodeData){
if(root!=null){
nodeData.push(root.data);
printAllPath(root.left, nodeData);
printAllPath(root.right, nodeData);
nodeData.pop();
}
if(root != null && root.left == null && root.right == null){
nodeData.push(root.data);
printStack(nodeData);
nodeData.pop();
}
}
Sorry about the formatting in last one.
Here's my approach based on the pre-order traversal and stack.
public static void printStack(Stack<Integer> nodeData){
Iterator<Integer> it = nodeData.iterator();
System.out.println("Start Stack");
while(it.hasNext()){
int data = it.next();
System.out.println(data);
}
System.out.println("End Stack");
}
public static void printAllPath(TreeNode root, Stack<Integer> nodeData){
if(root!=null){
nodeData.push(root.data);
printAllPath(root.left, nodeData);
printAllPath(root.right, nodeData);
nodeData.pop();
}
if(root != null && root.left == null && root.right == null){
nodeData.push(root.data);
printStack(nodeData);
nodeData.pop();
}
}
public void getPaths(TreeNode root, List<String> parentPaths) {
List<String> childPaths = new LinkedList<String>();
if(root.left == null && root.right == null) {
parentPaths.add(root.val + "");
}
if(root.left != null) {
getPaths(root.left, childPaths);
}
if(root.right != null) {
getPaths(root.right, childPaths);
}
for(String childPath : childPaths) {
parentPaths.add(root.val + "->" + childPath);
}
}
public List<String> getAllPaths(TreeNode node){
List<String> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(node);
Map<Integer, Integer> parents = new HashMap<>();
parents.put(node.val, -1);
while(!stack.isEmpty()){
TreeNode tmp = stack.pop();
if(tmp.left == null && tmp.right == null){
LinkedList<Integer> tmpRes = new LinkedList<>();
int num = tmp.val;
while(num != -1){
tmpRes.addFirst(num);
num = parents.get(num);
}
result.add(createPath(tmpRes));
}
if(tmp.left != null) {
stack.push(tmp.left);
parents.put(tmp.left.val, tmp.val);
}
if(tmp.right != null){
stack.push(tmp.right);
parents.put(tmp.right.val, tmp.val );
}
}
return result;
}
public String createPath(LinkedList list){
if(list.isEmpty()){
return "";
}
StringBuilder sb = new StringBuilder(list.removeFirst().toString());
while(list.isEmpty()){
sb.append("->");
sb.append(list.removeFirst().toString());
}
return sb.toString();
}
public List<String> getAllPaths(TreeNode node){
List<String> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(node);
Map<Integer, Integer> parents = new HashMap<>();
parents.put(node.val, -1);
while(!stack.isEmpty()){
TreeNode tmp = stack.pop();
if(tmp.left == null && tmp.right == null){
LinkedList<Integer> tmpRes = new LinkedList<>();
int num = tmp.val;
while(num != -1){
tmpRes.addFirst(num);
num = parents.get(num);
}
result.add(createPath(tmpRes));
}
if(tmp.left != null) {
stack.push(tmp.left);
parents.put(tmp.left.val, tmp.val);
}
if(tmp.right != null){
stack.push(tmp.right);
parents.put(tmp.right.val, tmp.val );
}
}
return result;
}
public String createPath(LinkedList list){
if(list.isEmpty()){
return "";
}
StringBuilder sb = new StringBuilder(list.removeFirst().toString());
while(list.isEmpty()){
sb.append("->");
sb.append(list.removeFirst().toString());
}
return sb.toString();
}
public List<String> PrintAllPaths(Node root)
{
if(root==null)
{
return null;
}
StringBuffer curpath = new StringBuffer();
curpath.append(root.val);
curpath.append("->");
List<String> ans = printPath(root,ans,curpath);
return ans;
}
public void printPath(Node root,List<String> ans,StringBuffer curpath)
{
if(root==null)
{
return;
}
if(root.left==null && root.right==null)
{
curpath.append(root.val);
curpath.append("->");
ans.add(curpath.toString());
curpath.deleteCharAt(curpath.size()-1);
}
if(root.left!=null)
{
curpath.append(root.val);
curpath.append("->");
printPath(root.left,ans,);
curpath.deleteCharAt(curpath.size()-1);
}
if(root.right!=null)
{
curpath.append(root.val);
curpath.append("->");
printPath(root.right,ans,);
curpath.deleteCharAt(curpath.size()-1);
}
return;
}
This is an Objective-C solution using recursion
-(void)getAllPathsFromRoot:(TreeNode *)root andResult:(NSMutableArray *)result andTemp:(NSMutableArray *)temp{
if(root == nil){
return;
}
[temp addObject:[NSNumber numberWithInt:root.value]];
if(root.left == nil && root.rigth == nil){
[result addObjectsFromArray:temp];
[result addObject:@"|"];
}
else{
if(root.left != nil){
[self getAllPathsFromRoot:root.left andResult:result andTemp:temp];
}
if(root.rigth != nil){
[self getAllPathsFromRoot:root.rigth andResult:result andTemp:temp];
}
}
[temp removeLastObject];
}
Recursive python solution
Output isn't exactly as asked, but an extra condition can be added to remove initial arrow
def getAllPaths(root):
if not root:
return [""]
all_paths = [ "->" + str(root.value) + path for path in getAllPaths(root.left)]
all_paths.extend([ "->" + str(root.value) + path for path in getAllPaths(root.right)])
return list(set(all_paths))
C++ solution
RootToLeafPath.hpp
//
// RootToLeafPath.hpp
//
#ifndef RootToLeafPath_hpp
#define RootToLeafPath_hpp
#include <stdio.h>
#include <vector>
#include <iostream>
#include <list>
#include <sstream>
using namespace std;
namespace RootToLeafPath {
class TreeNode {
public:
TreeNode( int val ) {
_value = val;
_left = _right = NULL;
}
~TreeNode() {
// free nodes memory
}
TreeNode* addLeft(int value) {
TreeNode* node = new TreeNode(value);
_left = node;
return _left;
}
TreeNode* addRight(int value) {
TreeNode* node = new TreeNode(value);
_right = node;
return _right;
}
bool amILeaf() const {
return (_right == NULL && _left == NULL);
}
vector<string> pathsToLeafs() {
_paths.clear();
list<int> path;
travers(this, path);
return _paths;
}
private:
void travers(TreeNode* node, list<int> path) {
if ( node == NULL ) {
return;
}
path.push_back(node->_value);
if (node->amILeaf()) {
ostringstream pathSS;
for (auto p : path) {
pathSS << p << "->";
}
string pathString;
pathString = pathSS.str();
pathString.erase(pathString.end()-2, pathString.end());
_paths.push_back(pathString);
}
else {
travers(node->_left, path);
travers(node->_right, path);
}
}
private:
static vector<string> _paths;
int _value;
TreeNode *_left, *_right;
};
}
#endif /* RootToLeafPath_hpp */
RootToLeafPath.cpp
#include "RootToLeafPath.hpp"
vector<string> RootToLeafPath::TreeNode::_paths;
TestCase
//
// main.cpp
//
#include <iostream>
#include <vector>
#include "google/RootToLeafPath.hpp"
using namespace std;
int main() {
RootToLeafPath::TreeNode root(1);
root.addLeft(2)->addRight(5);
root.addRight(3);
auto paths = root.pathsToLeafs();
for (auto p : paths) {
cout << p << endl;
}
return 0;
}
c++ solution
#include <string>
#include <vector>
#include <iostream>
using namespace std;
class Node
{
public:
int val;
Node* left;
Node* right;
Node(int num)
{
val = num;
left = NULL;
right = NULL;
};
};
bool getPath(Node* node, vector<string> &paths, string cur_path);
void getPathString(Node* root, vector<string> &all_paths)
{
string cur_path = "";
getPath(root, all_paths, cur_path);
}
bool getPath(Node* node, vector<string> &paths, string cur_path)
{
if(node != NULL)
{
cur_path += "->";
cur_path += std::to_string(node->val);
bool is_left = getPath(node->left,paths, cur_path);
bool is_right = getPath(node->right,paths, cur_path);
if(!is_left && !is_right)
{
paths.push_back(cur_path);
}
return 1;
}
else return 0;
}
int main(void)
{
vector<string> all_paths;
Node root(1);
root.left = new Node(2);
root.right = new Node(3);
root.left->left = new Node(4);
root.right->left = new Node(5);
root.left->right = new Node(6);
getPathString(&root,all_paths);
for(vector<string>::iterator i = all_paths.begin(); i!=all_paths.end();i++)
{
cout<<*i<<endl;
}
return 1;
}
c++ solution
#include <string>
#include <vector>
#include <iostream>
using namespace std;
class Node
{
public:
int val;
Node* left;
Node* right;
Node(int num)
{
val = num;
left = NULL;
right = NULL;
};
};
bool getPath(Node* node, vector<string> &paths, string cur_path);
void getPathString(Node* root, vector<string> &all_paths)
{
string cur_path = "";
getPath(root, all_paths, cur_path);
}
bool getPath(Node* node, vector<string> &paths, string cur_path)
{
if(node != NULL)
{
cur_path += "->";
cur_path += std::to_string(node->val);
bool is_left = getPath(node->left,paths, cur_path);
bool is_right = getPath(node->right,paths, cur_path);
if(!is_left && !is_right)
{
paths.push_back(cur_path);
}
return 1;
}
else return 0;
}
int main(void)
{
vector<string> all_paths;
Node root(1);
root.left = new Node(2);
root.right = new Node(3);
root.left->left = new Node(4);
root.right->left = new Node(5);
root.left->right = new Node(6);
getPathString(&root,all_paths);
for(vector<string>::iterator i = all_paths.begin(); i!=all_paths.end();i++)
{
cout<<*i<<endl;
}
return 1;
}
class Node(object):
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def all_root_to_leaf(self):
paths = []
data = str(self.data)
if not self.left and not self.right:
paths.append(data)
else:
child_paths = []
if self.left:
child_paths.extend(self.left.all_root_to_leaf())
if self.right:
child_paths.extend(self.right.all_root_to_leaf())
for path in child_paths:
paths.append(data + "->" + path)
return paths
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root the root of the binary tree
* @return all root-to-leaf paths
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
binaryTreePaths(root, result, "");
return result;
}
public void binaryTreePaths(TreeNode root, List<String> resultList, String resultString) {
if(root == null) return;
if(root.left == null && root.right == null) {
resultString = resultString + root.val;
resultList.add(resultString);
return;
}
binaryTreePaths(root.left, resultList, resultString + root.val + "->");
binaryTreePaths(root.right, resultList, resultString + root.val + "->");
}
}
class Node
attr_accessor :value, :left, :right
def initialize value
@value = value
@left = nil
@right = nil
end
end
class Tree
attr_accessor :root
def initialize
@root = nil
end
def paths node = @root
return [[node.value]] unless node.right || node.left
res = []
res += [[node.value]]
res += paths(node.left).map{|el| el += [node.value]} if node.left
res += paths(node.right).map{|el| el += [node.value]} if node.right
res
end
end
#include<iostream>
#include<vector>
#include<unordered_map>
#include<list>
using namespace std;
struct TreeNode{
int value;
TreeNode* left;
TreeNode* right;
};
void bfs(TreeNode* root, unordered_map<TreeNode*, TreeNode*>& parents, vector<TreeNode*>& leafs){
if(root->left == nullptr && root->right == nullptr) {
leafs.push_back(root);
return;
}
if(root->left != nullptr){
parents[root->left] = root;
bfs(root->left, parents, leafs);
}
if(root->right != nullptr){
parents[root->right] = root;
bfs(root->right, parents, leafs);
}
}
TreeNode* make_node(int value, list<TreeNode>& nodes){
nodes.push_back({value});
return &nodes.back();
}
void draw_path(TreeNode* leaf, unordered_map<TreeNode*, TreeNode*> parents){
while(parents.find(leaf) != parents.end()){
cout << leaf->value << " <-- ";
leaf = parents[leaf];
}
cout << leaf->value;
}
int main(){
list<TreeNode> nodes{};
TreeNode* root = make_node(0, nodes);
root->left = make_node(1, nodes);
root->right = make_node(2, nodes);
root->left->right = make_node(3, nodes);
unordered_map<TreeNode*, TreeNode*> parents {};
vector<TreeNode*> leafs{};
bfs(root, parents, leafs);
for(TreeNode* leaf:leafs){
draw_path(leaf, parents);
cout << endl;
}
}
Here's what I came up with. View the complete solution with comments, considerations, and test cases here - https://github.com/johndifini/javaAlgos/blob/master/BinaryTreePaths.java
- johndifini October 29, 2016public class BinaryTreePaths { private Deque<String> deque = new ArrayDeque<String>(); private List<String> result = new ArrayList<String>(); /** * @param root the root of the binary tree * @return all root-to-leaf paths */ public List<String> binaryTreePaths(TreeNode root) { // Write your code here if(root == null) return result; deque.add(Integer.toString(root.val)); // If we reached the end of a leaf, save it to the results if(root.left == null && root.right == null) { // @todo Verify requirement of "->" as the delimiter. Can it be ", " instead? String joined = String.join("->", deque); result.add(joined); } else { if(root.left != null) { binaryTreePaths(root.left); } if(root.right != null) { binaryTreePaths(root.right); } } // We are done processing this node, so crawl back up the tree deque.removeLast(); return result; } /** * Clear the results to reuse a BinaryTreePaths instance * * @todo What if the caller forgets to call clear before he calls binaryTreePaths again? Can we make this class more foolproof? */ public void clear() { result.clear(); } }