what is the difference between node structures of double linked list and binary tree?

Question

I was asked in a interview about the difference between node structures of Doubly linked list and binary Tree.

Doubly Linked List Struct

typedef struct
{
int data;
struct node * next;
struct node * prev;
}node;    

Binary Tree Struct

typedef struct
{
int data;
struct node * left;
struct node * right;
}node;  

1. In Doubly linked list, we use pointers for traversing back and front in a linearly arranged list.
   
2. But where as left & right pointers are used to access the left & right nodes.

I don't find any difference in node structure except the way they are used. Could you please give me some differences???

Answer 1

I think you have answered your own questions. Other than the obvious differences in names of the pointers (next/prev and left/right), the differences are:

• In a doubly linked list, if n.next links to m then m.prev links to n. This is not the case in a binary tree.
• In a doubly linked list, a node can have at most two links to it. In a binary tree, each node has at most one link to it.
• In a doubly linked list, it is possible to follows links and end up at the node where you started. This is not possible in a binary tree.

If the doubly linked list is also cyclic, the following also holds:

• In a cyclic doubly linked list with one node, n.next links to n and n.prev also links to n. This is not possible in a binary tree: n.left and n.right do not link to the same node.
• In a binary tree with one node, n.next and n.prev could point to no node (i.e., the tree is just a leaf node) but in a cyclic doubly linked list with one node both links always have a value (albeit to the same node).
• In a binary tree it is optional to have a value for either n.left or n.right. If the binary tree is not balanced, it could be that all nodes have a value for n.right but not for n.left. This is not the case for a cyclic doubly linked list where all pointers have a value.

In terms of structure and content the nodes are the same but the differences are in how the pointers are used and what their values can be.

Answer 2

You can generalize: both a doubly-linked list and a binary tree are examples of a directed graph in which each node can have at most two outgoing edges (since that's how many pointer fields there are in the struct).

Each data structure imposes additional restrictions (for example in both cases the whole graph is reachable from a root node, but only in the doubly-linked list is the whole graph reachable from every node). Those restrictions characterize the different data structures, but have no effect on the struct used to represent a node.

Sometimes you want a binary tree in which each node additionally has a pointer to its parent -- in that case the two structs would be different.

Answer 3

You are absolutely right: assuming the same payload type (in your case it is int), the binary layout of these two node types is identical. It is only the usage of the two pointers that makes the two node types different.

If you do not care about readability, you could use a node

typedef struct node {
    int data;
    struct node *p1;
    struct node *p2;
} node;

to represent both a binary tree and a doubly linked list. It wouldn't be a good idea, though, because the code would immediately become less recognizable to other programmers.