CODEWITHSUNDEEP
data-structurestree
shiv
shiv

Reputation: 1952

Why nodes of a binary tree have links only from parent to children?

Why nodes of a binary tree have links only from parent to children? I know tha there is threaded binary tree but those are harder to implement. A binary tree with two links will allow traversal in both directions iteratively without a stack or queue.

I do not know of any such design. If there is one please let me know.

Edit1: Let me conjure a problem for this. I want to do traversal without recursion and without using extra memory in form of stack or queue.

PS: I am afraid that I am going to get flake and downvotes for this stupid question.

Upvotes: 2

Views: 1966

Answers (3)

Kaz
Kaz

Reputation: 58666

Let me conjure a problem for this. I want to do traversal without recursion and without using extra memory in form of stack or queue.

Have you considered that the parent pointers in the tree occupy space themselves?

They add O(N) memory to the tree to store parent pointer in order not to use O(log N) space during recursion.

What parent pointers allow us to do is to support an API whereby the caller can pass a pointer to a node and request an operation on it like "find the next node in order" (for example).

In this situation, we do not have a stack which holds the path to the root; we just receive a node "out of the blue" from the caller. With parent pointers, given a tree node, we can find its successor in amortized constant time O(1).

Implementations which don't require this functionality can save space by not including the parent pointers in the tree, and using recursion or an explicit stack structure for the root to leaf traversals.

Upvotes: 0

rubyyhj
rubyyhj

Reputation: 51

It can be, however, we should consider the balance between the memory usage and the complexity.

Yeah you can traverse the binary tree with an extra link in each node, but actually you are using the same extra memory as you do the traversal with a queue, which even run faster.

What binary search tree good at is that it can implement many searching problems in O(logN). It's fast enough and memory saving.

Upvotes: 0

Luke1195
Luke1195

Reputation: 23

Some binary trees do require children to keep up with their parent, or even their grandparent, e.g. Splay Trees. However this is only to balance or splay the tree. The reason we only traverse a tree from the parent to the children is because we are usually searching for a specific node, and as long as the binary tree is implemented such that all left children are less than the parent, and all right children are greater than the parent (or vice-versa), we only need links in one direction to find that node. We start the search at the root and then iterate down, and if the node is in the tree, we are guaranteed to find it. If we started at a leaf, there is no guarantee we would find the node we want by going back to the root. The reason we don't have links from the child to the parent is because it is unnecessary for searches. Hope this helps.

Upvotes: 2

Related Questions