Skip to main content

Extract leaves of a binary tree in a doubly linked list

The problem discussed in this article involves extracting the leaves of a binary tree and arranging them in a doubly linked list. A binary tree is a hierarchical data structure where each node has at most two children – a left child and a right child. The problem requires extracting the leaf nodes (nodes with no children) from the binary tree and transforming them into a doubly linked list.

Problem Statement

Given a binary tree, we need to extract the leaf nodes from it and arrange them in a doubly linked list. The order of nodes in the linked list should correspond to the pre-order traversal of the original tree.

Example

Let's consider an example to understand the problem. Given the following binary tree:


         10
        /  \
       /    \
      6      8
     / \    / \
    2   3  7   5
   /         \   \
  9           -6  13

After extracting the leaf nodes, the pre-order traversal of the transformed tree will be: 10, 6, 2, 8, 7, 5. The extracted leaves will be arranged in a doubly linked list: 9, 3, -6, 13.

Idea to Solve

To solve this problem, we need to perform a pre-order traversal of the binary tree while extracting the leaf nodes. During the traversal, when we encounter a leaf node, we remove it from the tree and transform it into a doubly linked list node. We also adjust the links of the nodes accordingly.

Pseudocode

Here's the pseudocode that outlines the algorithm to extract leaves of a binary tree in a doubly linked list:

function extractLeaves(node):
    if node is not null:
        if node.left is null and node.right is null:
            node.right = front
            if front is not null:
                front.left = node
            front = node
            return null
        node.right = extractLeaves(node.right)
        node.left = extractLeaves(node.left)
        return node

Algorithm Explanation

  • We start by defining a front pointer in the BinaryTree class to keep track of the front of the doubly linked list.
  • The extractLeaves function takes a node as input and operates recursively.
  • When a leaf node is encountered (both left and right children are null), we transform it into a doubly linked list node.
  • We adjust the right and left pointers of the node to connect it with the previous and next nodes in the linked list.
  • If the front pointer is not null (indicating a non-empty list), we also adjust the left pointer of the front node.
  • The function then returns null, indicating that the leaf node should be removed from the tree.
  • During the recursion, we traverse the tree in a pre-order fashion.
  • At the end of the algorithm, the binary tree will be modified, and the linked list of leaf nodes will be created.

Code Solution

Time Complexity

  • The algorithm involves a pre-order traversal of the binary tree.
  • During the traversal, each node is processed once, and constant-time operations are performed to adjust the links.
  • Therefore, the time complexity of the algorithm is O(n), where n is the number of nodes in the binary tree.




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment