Leetcode Binary Tree Paths problem solution

YASH PAL,

In this Leetcode Binary Tree Paths problem solution we have given the root of a binary tree, return all root-to-leaf paths in any order. A leaf is a node with no children.

Leetcode Binary Tree Paths problem solution

Problem solution in Python.

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        if root is None:
            return []
        path = str(root.val)
        res = []
        self.traverse(root,path,res)
        return res
    
    def traverse(self, root, path, res):
        if root.left is None and root.right is None:
            res.append(path)
        if root.left is not None:
            self.traverse(root.left, path+"->"+str(root.left.val), res)
        if root.right is not None:
            self.traverse(root.right, path+"->"+str(root.right.val), res)

Problem solution in Java.

public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
    List<String> list = new ArrayList<String>();
    if(root == null)  return list;
    StringBuilder str = new StringBuilder();
    binaryHelper(root,list,str);
    return list;
}

private void binaryHelper(TreeNode root, List<String> list, StringBuilder str){
    if(root == null) return;
    StringBuilder newStr = new StringBuilder(str);
    if(newStr.length() != 0)
        newStr.append("->");
    newStr.append(root.val);
    if(root.left == null && root.right == null)
    {
        list.add(newStr.toString());
        return;
    }
        binaryHelper(root.left,list,newStr);
        binaryHelper(root.right,list,newStr);
}
}

Problem solution in C++.

vector<string> binaryTreePaths(TreeNode* root) 
    {
        if(root==NULL) return {};
        else
        {
            vector<string> lefty= binaryTreePaths(root->left);
            vector<string> righty= binaryTreePaths(root->right);
            vector<string> ans;
            string rooty=to_string(root->val);
            int l=lefty.size(), r=righty.size();
            if(l==0 and r==0) 
            {
                vector<string> v;
                v.push_back(rooty);
                return v;
            }
            for(int i=0;i<l;i++)
            {
                string s=rooty+"->"+lefty[i];
                ans.push_back(s);
            }
             for(int i=0;i<r;i++)
            {
                string s=rooty+"->"+righty[i];
                ans.push_back(s);
            }
            return ans;
        }
    }

Problem solution in C.

#define MAX_SIZE 1000

void pre_order_str(struct TreeNode *root, char ***res, int *res_size, char str[]) {
  
  if(NULL == root)
    return;

  char buf[MAX_SIZE];
  int append_size = 0;
  snprintf(buf, MAX_SIZE, "%d", root->val);
  append_size = strlen(buf);
  if(strnlen(str, MAX_SIZE) >= 1) {
    strncat(str, "->", MAX_SIZE);
    append_size += 2;
  }
  strncat(str, buf,MAX_SIZE);
  
  pre_order_str(root->left, res, res_size, str);
  pre_order_str(root->right, res, res_size, str);
  
  /*If leaf */
  if((!root->left) && (!root->right)) {    
    (*res_size)++;
    (*res) = realloc((*res), sizeof(char *) * (*res_size));
    int size = (*res_size) - 1;

    (*res)[size] = malloc(sizeof(char) * MAX_SIZE);
    strncpy((*res)[size], str, MAX_SIZE);
  }  
  
  /* when done with node remove ->val from str */
  str[strnlen(str, MAX_SIZE) - append_size] = '';  
}

char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
  
  char **result = malloc(sizeof(char *) * 1);
  if(NULL == result) {
    *returnSize = 0;
    return NULL;
  }
  
  char str[MAX_SIZE];
  str[0] = '';
  
  pre_order_str(root, &result, returnSize, str);
  
  return result;
  
}

coding problems