Find Leaves of Binary Tree

Jyothi
2 min readApr 6, 2022

Given the root of a binary tree, collect a tree's nodes as if you were doing this:

  • Collect all the leaf nodes.
  • Remove all the leaf nodes.
  • Repeat until the tree is empty.

Preorder traversal is better approach to this problem as we need to collect leaf nodes and remove those leaf nodes.

Solution is to write a utility function to collect and remove leaf nodes. Then call this function in a loop till the leaves of root node are null.

void getNrmLeafnodes(struct TreeNode* nd, struct TreeNode *parent, int **rar, int *curr_nodes, int *max_nodes, int left){
int *ar = *rar;
if (!nd) return;
if (!(nd->left) && !(nd->right)){
if (parent) {
if (left) parent->left = NULL;
else parent->right = NULL;
}
(*curr_nodes) ++;
if (*curr_nodes > *max_nodes){
*max_nodes +=10;
ar =(int *)realloc(ar, sizeof(int)*(*max_nodes));
}
ar[(*curr_nodes)-1] = nd->val;
*rar = ar;
return;
}
getNrmLeafnodes(nd->left, nd, rar, curr_nodes, max_nodes, 1);
getNrmLeafnodes(nd->right, nd, rar, curr_nodes, max_nodes, 0);
return;
}
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** findLeaves(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
int **res, *cols, rs, curr_nodes=0, max_nodes= 10;

int max_col=10, cur_col=0;

if (!root){ *returnSize = 0; return NULL;}

res = (int **)malloc(sizeof(int *)*max_col);
cols = (int *)malloc(sizeof(int )*max_col);

while (root->left || root->right){
if (cur_col == max_col){
max_col +=10;
res = (int **)realloc(res, sizeof(int *)*max_col);
cols = (int *)realloc(cols, sizeof(int )*max_col);
}
res[cur_col] = (int*)malloc(sizeof(int)*max_nodes);
cols[cur_col] = 0;
getNrmLeafnodes(root, NULL, &res[cur_col], &cols[cur_col], &max_nodes,0);
max_nodes = 10;
cur_col++;
}
if (cur_col == max_col){
max_col +=10;
res = (int **)realloc(res, sizeof(int *)*max_col);
cols = (int *)realloc(cols, sizeof(int )*max_col);
}
res[cur_col] = (int*)malloc(sizeof(int));
cols[cur_col] = 1;
res[cur_col][0] = root->val;
cur_col++;

*returnSize = cur_col;
*returnColumnSizes = cols;
return res;
}

--

--