Write a recursive function treeToList(Node root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes. The "previous" pointers should be stored in the "small" field and the "next" pointers should be stored in the "large" field. The list should be arranged so that the nodes are in increasing order. Return the head pointer to the new list. The operation can be done in O(n) time - - essentially operating on each node once. Try the problem directly, or see the hints below. Hint #1 The recursion is key. Trust that the recursive call on each sub-tree works and concentrate on assembling the outputs of the recursive calls to build the result. It's too complex to delve into how each recursive call is going to work -- trust that it did work and assemble the answer from there. Hint #2 The recursion will go down the tree, recursively changing the small and large sub-trees into lists, and then append those lists together with the parent node to make larger lists. Separate out a utility function append(Node a, Node b) that takes two circular doubly linked lists and appends them together to make one list which is returned. Writing a separate utility function helps move some of the complexity out of the recursive function.
Write a recursive function treeToList(Node root) that takes
an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out
of the tree nodes. The "previous" pointers should be stored in the "small" field and the "next"
pointers should be stored in the "large" field. The list should be arranged so that the nodes are in
increasing order. Return the head pointer to the new list. The operation can be done in O(n) time -
- essentially operating on each node once.
Try the problem directly, or see the hints below.
Hint #1
The recursion is key. Trust that the recursive call on each sub-tree works and concentrate on
assembling the outputs of the recursive calls to build the result. It's too complex to delve into how
each recursive call is going to work -- trust that it did work and assemble the answer from there.
Hint #2
The recursion will go down the tree, recursively changing the small and large sub-trees into lists,
and then append those lists together with the parent node to make larger lists. Separate out a utility
function append(Node a, Node b) that takes two circular doubly linked lists and appends them
together to make one list which is returned. Writing a separate utility function helps move some
of the complexity out of the recursive function.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
