The Tannenbaum series

A series of 7 single digits, that if added in sequence to create an unbalanced binary search tree, is considered a Tannenbaum series, in case:

• the left branch of the root has depth 3 and consists of ever-increasing numbers, and
• the right branch of the root has depth 3 and consists of ever-decreasing numbers, and
• it contains no duplicate digits.

Example: 4123765

      4
   /     \              
  /       \              
 /         \ 
1           7
 \         /
  2       6
   \     /
    3   5

Such a Tannenbaum series can be drawn using Tannenbaum search tree notation:

        4
       / \
      /   \
     /     \
    1_     _7
     /     \
    /       \
   /         \
  2_         _6
   /         \
  /           \
 /             \
3_______________5

This tree can be said to have O(Tannenbaum log n) search efficiency.

The task:

Write a program that takes a 7 digit sequence as input and determines if the 7 digits form a Tannenbaum series, then draws a valid Tannenbaum tree as proof. In case the series is invalid, the program gives no output.

The input can be assumed to be correct and containing no duplicates. The implementation can choose if to take the input either as integer or as a string. This is code golf, shortest source code per language wins.

Valid examples:

4123765
5234876

Invalid examples:

1234567
4321765
4123567

posted almost 4 years ago

CC BY-SA 4.0

Lundin‭

1149 reputation 17 43 134 70