Doubly Linked List Binary Search Tree in order Traversal

Question

I have a custom DLinkedList class, and this Binary Search Tree class and i would like it to return the doubly linked list using recursion, in order, but i don't know where to go from here

DLinkedList x = new DLinkedList();

public DLinkedList returnInOrderTraversal(){
    return IOT(rootNode); 
}

public DLinkedList IOT(BSTNode root){
    if(root == null) return x;
    IOT(root.leftChild)
    IOT(root.rightChild)
    x.add(//somehow add the root when the loop is finished)

    return x;

}

Doubly Linked List Class:

public class DLinkedList {

    private class Node {
        private int value;
        private Node nextNode;
        private Node prevNode;

        public Node(int v) {
            value = v;
            nextNode = null;
            prevNode = null;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int v) {
            value = v;
        }

        public Node getNextNode() {
            return nextNode;
        }

        public void setNextNode(Node n) {
            nextNode = n;
        }

        public Node getPrevNode() {
            return prevNode;
        }

        public void setPrevNode(Node n) {
            prevNode = n;
        }

    }

    // Holds a reference to the head and tail of the list
    private Node headNode;
    private Node tailNode;

    public DLinkedList() {
        headNode = null;
        tailNode = null;
    }

    public Object getHeadValue(){
        if (headNode == null)
            return null;
        return headNode.value;
    }

    public Object getTailValue(){
        if (tailNode == null)
            return null;
        return tailNode.value;
    }

    public void addAtHead(int o) {
        Node newNode = new Node(o); 
        newNode.setNextNode(headNode); 
        if (headNode != null)
            headNode.setPrevNode(newNode);
        headNode = newNode; 
        // special case for empty list
        if (tailNode == null)
            tailNode = newNode;
    }

    public void addAtTail(int o) {
        Node newNode = new Node(o);
        // this means that headNode == null too!
        if(tailNode == null){
            tailNode = newNode;
            headNode = newNode;
        }else{
            newNode.setPrevNode(tailNode);
            tailNode.setNextNode(newNode);
            tailNode = newNode;
        }
    }

    public Object deleteAtHead() {
        // list is empty 
        if(headNode == null){
            headNode = null;
            tailNode = null;
            return null;
        }
        // singleton: must update tailnode too
        if(headNode == tailNode){
            Object res = headNode.getValue();
            headNode = null;
            tailNode = null;
            return res;
        }

        Object res = headNode.getValue();
        headNode = headNode.getNextNode();
        headNode.setPrevNode(null);
        return res;
    }

    public Object deleteAtTail() {
        // list is empty 
        if(tailNode == null){
            headNode = null;
            tailNode = null;
            return null;
        }
        // singleton: must update tailnode too
        if(headNode == tailNode){
            Object res = tailNode.getValue();
            headNode = null;
            tailNode = null;
            return res;
        }
        Object res = tailNode.getValue();
        tailNode = tailNode.getPrevNode();
        tailNode.setNextNode(null);
        return res;
    }

}

Your setting nodes seems incorrect. If your addind Node n as next, so you should set n's prev to this node. — JamesR

BPS BPS · Accepted Answer · 2016-03-16T16:08:38

In order to get the elements in order, you want to do the add() after adding the left but before adding the right.

The add() itself can then just add the element at the end of the list.

Doubly Linked List Binary Search Tree in order Traversal

1 Answers