Pretty print a tree

Question

Let's say I have a binary tree data structure defined as follows

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

I have an instance of a tree as follows:

let x =
  Node
    (Node (Node (Nil,35,Node (Nil,40,Nil)),48,Node (Nil,52,Node (Nil,53,Nil))),
     80,Node (Node (Nil,82,Node (Nil,83,Nil)),92,Node (Nil,98,Nil)))

I'm trying to pretty-print the tree into something easy to interpret. Preferably, I'd like to print the tree in a console window like this:

        _______ 80 _______
       /                  \
    _ 48 _              _ 92 _
   /      \            /      \
 35       52         82       98
   \       \        /
    40      53    83

What's an easy way to get my tree to output in that format?

Heliopolis

Wows, seems trivial but probably very tricky. The top of the tree needs to know how many descendents in order to spread the 1st set of branches out wide enoughand so on. The logical method off my head now is to work your way from down-up. – Osteotomy

@o.k.w: its actually pretty easy to map the tree so that each node contains height information: pastebin.com/f1dd58c58 – Heliopolis

If you posted this as code golf, you would have gotten 20 implementations all in different languages. – Faviolafavonian

This article seems nice llimllib.github.com/pymag-trees – Foster

Answer 1

If you want it to be very pretty, you could steal about 25 lines of code from this blog entry to draw it with WPF.

But I'll code up an ascii solution shortly too, probably.

EDIT

Ok, wow, that was hard.

I'm not certain it's entirely correct, and I can't help but think there's probably a better abstraction. But anyway... enjoy!

(See the end of the code for a large example that is rather pretty.)

type 'a tree =    
    | Node of 'a tree * 'a * 'a tree
    | Nil

(*
For any given tree
     ddd
     / \
   lll rrr  
we think about it as these three sections, left|middle|right (L|M|R):
     d | d | d
     / |   | \
   lll |   | rrr  
M is always exactly one character.
L will be as wide as either (d's width / 2) or L's width, whichever is more (and always at least one)
R will be as wide as either ((d's width - 1) / 2) or R's width, whichever is more (and always at least one)
     (above two lines mean 'dddd' of even length is slightly off-center left)
We want the '/' to appear directly above the rightmost character of the direct left child.
We want the '\' to appear directly above the leftmost character of the direct right child.
If the width of 'ddd' is not long enough to reach within 1 character of the slashes, we widen 'ddd' with
    underscore characters on that side until it is wide enough.
*)

// PrettyAndWidthInfo : 'a tree -> string[] * int * int * int
// strings are all the same width (space padded if needed)
// first int is that total width
// second int is the column the root node starts in
// third int is the column the root node ends in
// (assumes d.ToString() never returns empty string)
let rec PrettyAndWidthInfo t =
    match t with
    | Nil -> 
        [], 0, 0, 0
    | Node(Nil,d,Nil) -> 
        let s = d.ToString()
        [s], s.Length, 0, s.Length-1
    | Node(l,d,r) ->
        // compute info for string of this node's data
        let s = d.ToString()
        let sw = s.Length
        let swl = sw/2
        let swr = (sw-1)/2
        assert(swl+1+swr = sw)  
        // recurse
        let lp,lw,_,lc = PrettyAndWidthInfo l
        let rp,rw,rc,_ = PrettyAndWidthInfo r
        // account for absent subtrees
        let lw,lb = if lw=0 then 1," " else lw,"/"
        let rw,rb = if rw=0 then 1," " else rw,"\\"
        // compute full width of this tree
        let totalLeftWidth = (max (max lw swl) 1)
        let totalRightWidth = (max (max rw swr) 1)
        let w = totalLeftWidth + 1 + totalRightWidth
(*
A suggestive example:
     dddd | d | dddd__
        / |   |       \
      lll |   |       rr
          |   |      ...
          |   | rrrrrrrrrrr
     ----       ----           swl, swr (left/right string width (of this node) before any padding)
      ---       -----------    lw, rw   (left/right width (of subtree) before any padding)
     ----                      totalLeftWidth
                -----------    totalRightWidth
     ----   -   -----------    w (total width)
*)
        // get right column info that accounts for left side
        let rc2 = totalLeftWidth + 1 + rc
        // make left and right tree same height        
        let lp = if lp.Length < rp.Length then lp @ List.init (rp.Length-lp.Length) (fun _ -> "") else lp
        let rp = if rp.Length < lp.Length then rp @ List.init (lp.Length-rp.Length) (fun _ -> "") else rp
        // widen left and right trees if necessary (in case parent node is wider, and also to fix the 'added height')
        let lp = lp |> List.map (fun s -> if s.Length < totalLeftWidth then (nSpaces (totalLeftWidth - s.Length)) + s else s)
        let rp = rp |> List.map (fun s -> if s.Length < totalRightWidth then s + (nSpaces (totalRightWidth - s.Length)) else s)
        // first part of line1
        let line1 =
            if swl < lw - lc - 1 then
                (nSpaces (lc + 1)) + (nBars (lw - lc - swl)) + s
            else
                (nSpaces (totalLeftWidth - swl)) + s
        // line1 right bars
        let line1 =
            if rc2 > line1.Length then
                line1 + (nBars (rc2 - line1.Length))
            else
                line1
        // line1 right padding
        let line1 = line1 + (nSpaces (w - line1.Length))
        // first part of line2
        let line2 = (nSpaces (totalLeftWidth - lw + lc)) + lb 
        // pad rest of left half
        let line2 = line2 + (nSpaces (totalLeftWidth - line2.Length))
        // add right content
        let line2 = line2 + " " + (nSpaces rc) + rb
        // add right padding
        let line2 = line2 + (nSpaces (w - line2.Length))
        let resultLines = line1 :: line2 :: ((lp,rp) ||> List.map2 (fun l r -> l + " " + r))
        for x in resultLines do
            assert(x.Length = w)
        resultLines, w, lw-swl, totalLeftWidth+1+swr
and nSpaces n = 
    String.replicate n " "
and nBars n = 
    String.replicate n "_"

let PrettyPrint t =
    let sl,_,_,_ = PrettyAndWidthInfo t
    for s in sl do
        printfn "%s" s

let y = Node(Node (Node (Nil,35,Node (Node(Nil,1,Nil),88888888,Nil)),48,Node (Nil,777777777,Node (Nil,53,Nil))),     
             80,Node (Node (Nil,82,Node (Nil,83,Nil)),1111111111,Node (Nil,98,Nil)))
let z = Node(y,55555,y)
let x = Node(z,4444,y)

PrettyPrint x
(*
                                   ___________________________4444_________________
                                  /                                                \
                      ________55555________________                         ________80
                     /                             \                       /         \
            ________80                      ________80             _______48         1111111111
           /         \                     /         \            /        \            /  \
   _______48         1111111111    _______48         1111111111 35         777777777  82   98
  /        \            /  \      /        \            /  \      \             \       \
35         777777777  82   98   35         777777777  82   98     88888888      53      83
  \             \       \         \             \       \            /
  88888888      53      83        88888888      53      83           1
     /                               /
     1                               1
*)     

Citreous

+1: awesomeness! Its definitely a lot harder than it looks (and I bet the J solution isn't more than 50 chars). I'll see if I can come up with something a little simpler :) – Heliopolis

Answer 2

If you don't mind turning your head sideways, you can print the tree depth first, one node to a line, recursively passing the depth down the tree, and printing depth*N spaces on the line before the node.

Here's Lua code:

tree={{{nil,35,{nil,40,nil}},48,{nil,52,{nil,53,nil}}},
      80,{{nil,82,{nil,83,nil}},92 {nil,98,nil}}}

function pptree (t,depth) 
  if t ~= nil
  then pptree(t[3], depth+1)
    print(string.format("%s%d",string.rep("  ",depth), t[2]))
    pptree(t[1], depth+1)
  end
end

Test:

> pptree(tree,4)
        98
      92
          83
        82
    80
          53
        52
      48
          40
        35
> 

Profit

This scheme is easy and quite readable in practice. For each tree node of depth n, print out the node type (e.g., 80) indented n, then print the children (recusisively) indented depth N+1. – Deserving

I'm actually printing my trees sideways using exactly what you describe (code here: pastebin.com/f1a50baef ), and it works for smaller trees. However, part algorithm-curiosity and part preference-for-vertical-trees has me in search of a better visual representation. – Heliopolis

Answer 3

Maybe this can help: Drawing Trees in ML

Hanfurd

Answer 4

Although it's not exactly the right output, I found an answer at http://www.christiankissig.de/cms/files/ocaml99/problem67.ml :

(* A string representation of binary trees

Somebody represents binary trees as strings of the following type (see example opposite):

a(b(d,e),c(,f(g,)))

a) Write a Prolog predicate which generates this string representation, if the tree 
is given as usual (as nil or t(X,L,R) term). Then write a predicate which does this 
inverse; i.e. given the string representation, construct the tree in the usual form. 
Finally, combine the two predicates in a single predicate tree_string/2 which can be 
used in both directions.

b) Write the same predicate tree_string/2 using difference lists and a single 
predicate tree_dlist/2 which does the conversion between a tree and a difference 
list in both directions.

For simplicity, suppose the information in the nodes is a single letter and there are 
no spaces in the string. 
*)

type bin_tree = 
    Leaf of string
|   Node of string * bin_tree * bin_tree
;;

let rec tree_to_string t =
    match t with
            Leaf s -> s
    |       Node (s,tl,tr) -> 
                    String.concat "" 
                            [s;"(";tree_to_string tl;",";tree_to_string tr;")"]
;;

Enthuse

Answer 5

This is an intuition, I'm sure someone like Knuth had the idea, I'm too lazy to check.

If you look at your tree as an one dimensional structure you will get an array (or vector) of length L This is easy to build with an "in order" recursive tree traversal: left,root,right some calculations must be done to fill the gaps when the tree is unbalanced

2 dimension

                    _______ 80 _______
                   /                  \
                _ 48 _              _ 92 _
               /      \            /      \
             35       52         82       98
               \       \        /
                40      53    83
    
    

1 dimension :

             35 40 48   52 53 80 83 82    92    98   
           0 1  2  3  4  5  6  7  8  9 10 11 12 13 14 

The pretty printed tree can be build using this array (maybe with something recursive) first using values at L/2 position, the X position is the L/2 value * the default length (here it is 2 characters)

                              80
    
    then (L/2) - (L/4)  and  (L/2) + (L/4) 
    
                   48                    92
    then L/2-L/4-L/8, L/2-L/4+L/8, L/2+L/4-L/8 and L/2+L/4+L/8 
    
              35        52         82          98
    
    ...

Adding pretty branches will cause more positional arithmetics but it's trivial here

You can concatenate values in a string instead using an array, concatenation will de facto calculate the best X postion and will allow different value size, making a more compact tree. In this case you will have to count the words in the string to extract the values. ex: for the first element using the L/2th word of the string instead of the L/2 element of the array. The X position in the string is the same in the tree.

N 35 40 48 N 52 53 80 83 82 N 92 N 98 N 
                   80
        48                    92
  35         52          82        98
     40         53    83                  

Borderland