CODEWITHSUNDEEP
calgorithm
Bglen
Bglen

Reputation: 69

C binary tree, How to make list from tree leaves

I need to build list of all the leaves in tree
for example, I have the following tree:

    6
   / \
  4   3
 /\   /\
1  2 5  7

treeNode typedef

typedef struct  treeNode {
    int data;
    struct treeNode* parent;
    struct treeNode* left;
    struct treeNode* right;
} TreeNode;

my list should be 1->2->5->7

list typedef

typedef struct list {
        ListNode* head;
        ListNode* tail;
    } List;

listNode typedef

  typedef struct listNode {
        int data;
        struct listNode* next;
    } ListNode;

Listnode->data = TreeNode->data; (the listnode struct data)

The function should be generic, I tired several recursion functions but none worked

Any ideas? Thanks in advance.

Upvotes: 0

Views: 1560

Answers (2)

tulians
tulians

Reputation: 448

This can be done with recursion, as you tried. What you have to do is first check whether you've reached a leaf node, ie. if left and right pointers are NULL, and in that case you add the node to the list. The pseudo-code looks like this:

getLeavesList(root) {
    if root is NULL: return
    if root is leaf_node: add_to_leaves_list(root)
    getLeavesList(root -> left)
    getLeavesList(root -> right)
}

You can adapt this code to any programming language. So, if the root is NULL, this is, if the function received no valid pointer, then return an error message. If the root is a leaf, this is, if both left and right child nodes are NULL, the you have to add it to the list of leaf nodes. Then you recursively call the function with the left and right child nodes.

Upvotes: 0

John Bupit
John Bupit

Reputation: 10618

The basic idea would be to traverse the tree in-order, and push every leaf node you encounter to the list. Something like the following:

populateList(node)
  if(node == null) return

  populateList(node->left)

  if (node->left == null && node->right == null)
    pushToList(node)
    return

  populateList(node->right)

Upvotes: 4

Related Questions