Converting binary search tree to linked list

Question

I am trying to convert a binary search tree to a linked list. The linked list should have the smaller numbers in the front and the larger numbers in the back (smallest to largest). I need to create a function that takes in a binary search tree tree and outputs a linked list.

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

Here's my binary search tree. I need to make the linked list this way: 1, 2, 3, 4, 5, 6, 7. Here's my current code:

node<int>* makeLinkedList(binary_tree_node<int>* root_ptr);

int main()
{
    binary_tree_node<int> *s1 = sample1();  //Creates the tree

    node<int>* node1 = makeLinkedList(s1);  //invokes function to make a linked list

    //Loop to print out the values of the linked list
    for (node1; node1 != NULL; node1 = node1->link()){
        cout<<node1->data()<<endl;
    }
}

node<int>* makeLinkedList(binary_tree_node<int>* root_ptr){
    node<int>* left;

    if (root_ptr == NULL) {
            return NULL;
    }

    else{

        left = makeLinkedList(root_ptr->left()); 
        list_head_insert(left, root_ptr->data());  //list_head_insert inserts a new entry at the head of the linked list
        return left;
    }
}

When I run my code, the output is 4, 2, 1. I just don't understand how I can convert this binary search tree into a linked list from smallest to largest. I've tried putting list_head_insert function on top of the recursive call, but the output is nothing and the list is empty.

SenselessCoder · Accepted Answer · 2016-11-16 00:32:39Z

3

So in other words you want this in sorted form in your linked list.

There's a way of traversal for that: In-Order Traversal. See here for more info on traversals.

So how to do this, though? As a hint I'll give you a function to "print" the contents of this BST in-order. That should get you rolling. (As after figuring out how to get contents of the tree in-order, all you have to do is just call an insert function to your list)

void print_in_order(Node* t) {
    if(!t)
        return;
    print_in_order(t->left);
    cout << t->data;
    print_in_order(t->right);
}

answered Nov 16, 2016 at 0:32

SenselessCoder

1,16912 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

user2896120 Over a year ago

I understand in order traversal and how to print the contents of the tree, but I don't know how I can insert the contents of those nodes to my linked list.

SenselessCoder Over a year ago

It's quite straightforward. Using the method above, with a few modifications, you can add elements to your list. Simply after getting an element in this recursive manner, call a function that'll help insert an element to the list. As an additional hint, when do you actually get to have an element from the tree? Do you have to really go until t is null? When can you stop?

user2896120 Over a year ago

makeLinkedList(root_ptr->left());  		list_head_insert(list2, root_ptr->data()); 		makeLinkedList(root_ptr->right());  		 		return list2;

This is what I have right now, the program compiles, but it exits out because of some problem. Is this what you are talking about doing?

SenselessCoder Over a year ago

Yes, that should work. Make sure that you check if the pointer recevied is null.

user2896120 Over a year ago

I have a base case statement that checks if the pointer is null like this: if (root_ptr == NULL) { return NULL; }Is this what you mean?

|

Sk Monjurul Haque · Accepted Answer · 2022-02-10 14:46:09Z


class HeadAndTail<T> {
    LinkedListNode<T> head;
    LinkedListNode<T> tail;

    public HeadAndTail() {
        this.head = null;
        this.tail = null;
    }

}

public class Solution {

     public static LinkedListNode<Integer> constructLinkedList(BinaryTreeNode<Integer> root) {
        return construct(root).head;
    }

    public static HeadAndTail<Integer> construct(BinaryTreeNode<Integer> root) {

        if(root == null) {
            return new HeadAndTail<>();
        }

        if(isLeafNode(root)) {
            LinkedListNode<Integer> node = new LinkedListNode<>(root.data);
            HeadAndTail<Integer> headAndTail = new HeadAndTail<>();
            headAndTail.head = node;
            headAndTail.tail = node;
            return headAndTail;
        }

        LinkedListNode<Integer> node = new LinkedListNode<>(root.data);
        HeadAndTail<Integer> forLeftPart = construct(root.left);
        HeadAndTail<Integer> forRightPart = construct(root.right);

        node.next = forRightPart.head;
        HeadAndTail<Integer> headAndTail = new HeadAndTail<>();

        //if left part is null
        if(forLeftPart.tail != null) {
            forLeftPart.tail.next = node;
            headAndTail.head = forLeftPart.head;
        } else{
            headAndTail.head = node;
        }

        //if right part is null
        if(forRightPart.tail != null) {
            headAndTail.tail = forRightPart.tail;
        } else {
            headAndTail.tail = node;
        }

        return headAndTail;
    }


}

Collectives™ on Stack Overflow

Converting binary search tree to linked list

2 Answers 2

11 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

11 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related