Question Binary tree threaded

[quentisa]

Hello everyone, I'm expected to develop the ThreadedNode() class, but I'm having some difficulties with it.

I understand that a threaded binary tree of a binary tree is generated by assigning every null left child to the node in the inorder traversal's predecessor and every null right child to the node in the inorder traversal's successor. My issue, though, begins with the constructor // thread the binary tree when given the root public ThreadedNode(BinaryNode root)

According to this article, a frequent approach to generate threaded binary trees is using a phoney head. This simplifies the construction of single node trees and simplifies the constructor. Is that correct?
I understand that it accepts a binaryNode and that I must construct a threaded tree, but how do I do so?

 

[Bot]

Yes, using a phoney head node (also known as a dummy node) is a common and convenient approach to simplify the construction of threaded binary trees. It helps in handling edge cases and provides a consistent starting point for traversals.

Here's a step-by-step explanation on how to construct the `ThreadedNode` class and thread the binary tree:

1. Define the `ThreadedNode` class, which should have a reference to a `BinaryNode` object, left and right pointers (which can also be of `ThreadedNode` type), and two boolean variables `leftThread` and `rightThread` to indicate if the left and right pointers are threads or not.

```java
public class ThreadedNode {
BinaryNode node;
ThreadedNode left, right;
boolean leftThread, rightThread;

public ThreadedNode(BinaryNode node) {
this.node = node;
left = null;
right = null;
leftThread = false;
rightThread = false;
}
}
```

2. Create the constructor `ThreadedNode(BinaryNode root)` that accepts a `BinaryNode` as the root of the binary tree to be threaded.

3. Initialize a dummy head node with null values and set its `rightThread` as false. This head node will serve as the starting point for the threaded tree construction.

```java
public ThreadedNode(BinaryNode root) {
this.node = null;
left = this;
right = this;
leftThread = true;
rightThread = false;

if (root == null) {
return;
}

// Continue with the threading process
}
```

4. Start the threading process. Perform an inorder traversal on the binary tree, and for each null left or right child, create a thread pointing to the inorder predecessor or successor, respectively.

You can create a helper function called `threadInOrder` that recursively threads the tree.

```java
private ThreadedNode prevNode = null;

private void threadInOrder(BinaryNode root) {
if (root == null) {
return;
}

// Traverse the left subtree
threadInOrder(root.left);

// Create a new ThreadedNode for the current BinaryNode
ThreadedNode currThreadedNode = new ThreadedNode(root);

// If the previous ThreadedNode exists
if (prevNode != null) {
// Set the right pointer of the previous ThreadedNode to the current ThreadedNode
prevNode.right = currThreadedNode;
prevNode.rightThread = true;

// Set the left pointer of the current ThreadedNode to the previous ThreadedNode
currThreadedNode.left = prevNode;
currThreadedNode.leftThread = true;
}

// Update the previous ThreadedNode to the current ThreadedNode
prevNode = currThreadedNode;

// Traverse the right subtree
threadInOrder(root.right);
}
```

5. Call the `threadInOrder` function in the constructor, passing the root of the binary tree as an argument.

```java
public ThreadedNode(BinaryNode root) {
// ...
// Initialize the dummy head node
// ...

// Start the threading process
threadInOrder(root);
}
```

Now, you should be able to construct a threaded binary tree using the `ThreadedNode(BinaryNode root)` constructor.