Create a singly linked list of Leaf nodes from a binary tree

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode
{
struct TreeNode *left, *right, *next;
int data;

}TreeNode;

typedef TreeNode * Tree;

void LeafLinked(Tree t, TreeNode **prevLeaf, TreeNode **head)
{
if(t) {

if(t->left == NULL && t->right == NULL) { //leaf

if(*head == NULL)
*head = t;

else if(*prevLeaf)
(*prevLeaf)->next = t;

*prevLeaf = t;
}
else { //at least one child
LeafLinked(t->left, prevLeaf, head);
LeafLinked(t->right, prevLeaf, head);
}
}
}


/*Utilities*/

inline TreeNode * makeTreeNode(int data)
{
TreeNode *n = calloc(sizeof(TreeNode), 1);
n->data = data;

return n;
}

inline void printList(Tree t)
{
while(t)
{
printf("%d ", t->data);
t = t->next;
}
printf("\n");
}

int main()
{
/*level 0*/
Tree t = makeTreeNode(10);

/*level 1*/
t->left = makeTreeNode(20);
t->right = makeTreeNode(30);


/*level 2*/
t->left->left = makeTreeNode(40);
t->left->right = makeTreeNode(70);
t->right->left = makeTreeNode(50);
t->right->right = makeTreeNode(60);

/*level 3*/
t->left->left->left = makeTreeNode(70);
t->right->right->left = makeTreeNode(60);
t->right->right->right = makeTreeNode(160);

/*Empty List head*/
TreeNode *head = NULL, *prevLeaf = NULL;

/*Convert tree to list*/
LeafLinked(t, &prevLeaf, &head);

/*print list*/
printList(head);


return 0;
}

Python Version:

class BinaryTree:

def __init__(self, e):
self.left = self.right = self.next = None
self.data = e


def LinkLeaves(t):

if t:
if t.left or t.right:

for x in LinkLeaves(t.left):
yield x

for x in LinkLeaves(t.right):
yield x
else:
yield t

def printList(t):

while t:
print t.data,
t = t.next
print

def main():

t = BinaryTree(10);

t.left = BinaryTree(20)
t.right = BinaryTree(30)

t.left.left = BinaryTree(40)
t.left.right = BinaryTree(70)
t.right.left = BinaryTree(50)
t.right.right = BinaryTree(60)

t.left.left.left = BinaryTree(70)
t.right.right.left = BinaryTree(60)
t.right.right.right = BinaryTree(160)

head = None
prevLeaf = None

for x in LinkLeaves(t):
if head is None:
head = x
else:
prevLeaf.next = x

prevLeaf = x

printList(head)


if __name__ == '__main__':
main()
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s