An algorithm to operate on a binary tree leaves?

0
votes

I didn't systematically learn the Data Structure and Algorithm course in the uni (just read some books) and would like to ask if there is a well-defined algorithm to do the following work for a binary tree:

For a given binary tree and a positive integer n, search its leaves. If the difference between the depth of the two adjacent leaves (imagine all leaves are display as an array, so two adjacent leaves may be in two different sub-trees) is larger than n. Subdivide the leaf with lower depth. Recursively do this operation until no subdivision is required.

The following figure is a demonstration, for n: enter image description here

Since leaf 1's depth is smaller than leaf 2 by 2, leaf 1 need to be subdivided:enter image description here

Now no further subdivision is required.

1
algorithmtreebinary-tree

1 Answers

0
votes
  1. Initialize P as empty
  2. DFS the remaining part of the tree until you are in a leaf L; exit if no more leaves
  3. Compare the current depth DL with the depth DP of the previous leaf P; go to [5] if P is empty
  4. If |DL – DP| ≥ N, split either L (when DL < DP) or P (otherwise)
  5. Consider L the new P and go to [2]

Repeat this until the tree converges (i.e. until no splits can be performed).