Extract Leaves of a Binary Tree in a Doubly Linked List | GeeksforGeeks

Extract Leaves of a Binary Tree in a Doubly Linked List | GeeksforGeeks

Given a Binary Tree, extract all leaves of it in a Doubly Linked List (DLL). Note that the DLL need to be created in-place.
We need to traverse all leaves and connect them by changing their left and right pointers. We also need to remove them from Binary Tree by changing left or right pointers in parent nodes. There can be many ways to solve this. In the following implementation, we add leaves at the beginning of current linked list and update head of the list using pointer to head pointer. Since we insert at the beginning, we need to process leaves in reverse order. For reverse order, we first traverse the right subtree then the left subtree. We use return values to update left or right pointers in parent nodes.

struct Node* extractLeafList(struct Node *root, struct Node **head_ref)

{

   // Base cases

   if (root == NULL)  return NULL;

   if (root->left == NULL && root->right == NULL)

   {

       // This node is going to be added to doubly linked list

       // of leaves, set right pointer of this node as previous

       // head of DLL. We don't need to set left pointer as left

       // is already NULL

       root->right = *head_ref;

       // Change left pointer of previous head

       if (*head_ref != NULL) (*head_ref)->left = root;

       // Change head of linked list

       *head_ref = root;

       return NULL;  // Return new root

   }

   // Recur for right and left subtrees

   root->right = extractLeafList(root->right, head_ref);

   root->left  = extractLeafList(root->left, head_ref);

   return root;

}

Read full article from Extract Leaves of a Binary Tree in a Doubly Linked List | GeeksforGeeks

Transform a BST to greater sum tree | GeeksforGeeks

http://www.geeksforgeeks.org/transform-bst-sum-tree/
Given a BST, transform it into greater sum tree where each node contains sum of all nodes greater than that node.
Key Point: Using reverse inorder traversal to get decreasing order. Accumulative Sum.

The idea is to traverse BST in reverse inorder. Reverse inorder traversal of a BST gives us keys in decreasing order. Before visiting a node, we visit all greater nodes of that node. While traversing we keep track of sum of keys which is the sum of all the keys greater than the key of current node.

// Recursive function to transform a BST to sum tree.

// This function traverses the tree in reverse inorder so

// that we have visited all greater key nodes of the currently

// visited node
void transformTreeUtil(struct Node *root, int *sum)

{

   // Base case

   if (root == NULL)  return;

   // Recur for right subtree

   transformTreeUtil(root->right, sum);

   // Update sum

   *sum = *sum + root->data;

   // Store old sum in current node

   root->data = *sum - root->data;

   // Recur for left subtree

   transformTreeUtil(root->left, sum);

}

// A wrapper over transformTreeUtil()

void transformTree(struct Node *root)

{

    int sum = 0; // Initialize sum

    transformTreeUtil(root, &sum);

}

Method 1 (Naive):
This method doesn’t require the tree to be a BST. Following are steps.
1. Traverse node by node(Inorder, preorder, etc.)
2. For each node find all the nodes greater than that of the current node, sum the values. Store all these sums.
3. Replace each node value with their corresponding sum by traversing in the same order as in Step 1.
This takes O(n^2) Time Complexity.
Also check http://www.geeksforgeeks.org/convert-bst-to-a-binary-tree/
Read full article from Transform a BST to greater sum tree | GeeksforGeeks