Algorithm to Render a Horizontal Binary-Ish Tree in Text/Ascii Form

Algorithm to Render a Horizontal Binary-ish Tree in Text/ASCII form

If there are N end nodes, there must be N-1 internal nodes with 2 children. (There can be any number of internal nodes with 1 child, which we will have to count to get the depths but otherwise ignore.) Generating the tree is thus equivalent to positioning these nodes on a grid, where:

the number of rows in the grid is N
I think the number of columns is between 1+floor(log2(N)) and 2*N-1, depending on how much overlap there is; this probably doesn't matter much for our purposes, though
each endpoint appears on a different row
all nodes at the same depth appear in the same column
all internal nodes appear on the same row as their rightmost descendant endpoint

So, let's see:

Walk the tree depth-first, right-to-left.
For each endpoint, record its depth and label.
For each 2-child internal, record its depth, label and the indices of both rightmost and leftmost child endpoints.
Sort the whole lot by depth -- this gives you the column ordering, with the number of distinct depths giving the actual number of columns. (All other ordering should come out automatically from the walk, I think, but that's not the case here because any branch can be any depth.)
Place all the nodes in the grid.
Mark empty cells to the right of each non-endpoint node as horizontal branches.
Mark empty cells down from each internal node to the row above its left child as vertical branches, and the cell at the level of the left child as a junction.
Print with appropriate ASCII decoration.

Update:

As you say, the positioning is enough to unambiguously determine the connections, but you still need to do some bottom-up work to get that right, so I'd probably still do the "mark" steps during the grid building.

I sort of thought the printing was trivial enough to gloss over, but:

Iterate down each column and determine the column width as size of fixed elements + max label length + floor(log10(depth) + 1). (Fixed elements might be [ and ]-, for example. We can substitute ]\n as the suffix for endpoints.)
For each row
- for each column
  - if cell contains a node or endpoint
    - print fixed prefix
    - print label
    - print depth
    - print fill spaces (max label length - current label length)
    - print appropriate suffix
    - if node is an endpoint, skip to next row
  - if cell is empty, print fill spaces to width of column
  - if cell contains a vertical, print some chosen prefix number of spaces, a bar, and fill with spaces
  - if cell contains a junction, print some chosen prefix number of spaces, a backslash, and fill with hyphens
  - if cell contains a horizontal, print full column width of hyphens

Converting this to print diagonals might be easiest if you generate the straight version first and then do some substitutions in the character array -- otherwise you can get cases where you're rendering a long vertical branch in a different column than the one in which it originated.

At some point I may try to put this into code, but it probably won't be today -- stuff to do!

print a binary tree on its side

Here's some code that implements the general, recursive approach described elsewhere. The internal representation of a tree is either a string (leaf) or a tuple (pair) of sub-nodes. The internal representation of the intermediate "fragment" of a node is the tuple (above, below, lines), where above and below are number of lines above and below the root, and lines is an iterator over each partial line (without spaces to the left).

#!/usr/local/bin/python3.3

from itertools import chain
from random import randint

def leaf(t):
    return isinstance(t, str)

def random(n):
    def extend(t):
        if leaf(t):
            return (t+'l', t+'r')
        else:
            l, r = t
            if randint(0, 1): return (l, extend(r))
            else: return (extend(l), r)
    t = ''
    for _ in range(n-1): t = extend(t)
    return t

def format(t):
    def pad(prefix, spaces, previous):
        return prefix + (' ' * spaces) + previous
    def merge(l, r):
        l_above, l_below, l_lines = l
        r_above, r_below, r_lines = r
        gap = r_below + l_above
        gap_above = l_above
        gap_below = gap - gap_above
        def lines():
            for (i, line) in enumerate(chain(r_lines, l_lines)):
                if i < r_above:
                    yield ' ' + line
                elif i - r_above < gap_above:
                    dash = '_' if i - r_above == gap_above - 1 else ' '
                    if i < r_above + r_below:
                        yield pad(dash + '/', 2 * (i - r_above), line)
                    else:
                        yield pad(dash + '/', 2 * gap_below - 1, line)
                elif i - r_above - gap_above < gap_below:
                    if i < r_above + r_below:
                        yield pad(' \\', 2 * gap_above - 1, line)
                    else:
                        spaces = 2 * (r_above + gap_above + gap_below - i - 1)
                        yield pad(' \\', spaces, line)
                else:
                    yield ' ' + line
        return (r_above + gap_above, gap_below + l_below, lines())
    def descend(left, t):
        if leaf(t):
            if left:
                return (1, 0, [t])
            else:
                return (0, 1, [t])
        else:
            l, r = t
            return merge(descend(True, l), descend(False, r))
    def flatten(t):
        above, below, lines = t
        for (i, line) in enumerate(lines):
            if i < above: yield (' ' * (above - i - 1)) + line
            else: yield (' ' * (i - above)) + line
    return '\n'.join(flatten(descend(True, t)))

if __name__ == '__main__':
    for n in range(1,20,3):
        tree = random(n)
        print(format(tree))

Here's some example output:

          _/rrrr
        _/ \_/rrrlr
       / \   \rrrll
     _/   \_/rrlr
    / \     \rrll
   /   \   _/rlrr
  /     \_/ \rlrl
_/        \_/rllr
 \          \_/rlllr
  \           \rllll
   \        _/lrrr
    \     _/ \lrrl
     \   / \_/lrlr
      \_/    \lrll
        \   _/llrr
         \_/ \llrl
           \_/lllr
             \_/llllr
               \lllll

And a bit more asymmetric one that shows, perhaps, why I don't pad lines with spaces to the left until the end (via flatten). If the lower half had been padded on the left some of the upper arm would cross the padded area.

               _/rrrrr
             _/ \rrrrl
           _/ \rrrl
         _/ \_/rrlr
        / \   \rrll
       /   \_/rlr
      /      \rll
     /        /lrrr
    /       _/  _/lrrlrr
   /       / \_/ \lrrlrl
  /       /    \lrrll
_/      _/     _/lrlrrr
 \     / \   _/ \lrlrrl
  \   /   \_/ \lrlrl
   \_/      \lrll
     \      _/llrrr
      \   _/ \llrrl
       \_/ \llrl
         \lll

It's the "obvious" recursive algorithm - the devil is in the details. It was easiest to write without the "_", which makes the logic slightly more complex.

Perhaps the only "insight" is gap_above = l_above - that's saying that the right "arm" has the length of the right side of the left subtree (you'll need to read that a few times). It makes things relatively balanced. See the asymmetric example above.

A good way of understanding things in more detail is to modify the pad routine to take a character instead of ' ' and give a different character for each call. Then you can see exactly which logic generated which space. This is what you get using A. B, C and D for the calls to pad from top to bottom, above (obviously there's no character when the amount of space is zero):

             _/rrrr
            / \rrrl
          _/B _/rrlrr
         / \_/ \rrlrl
        /AA  \rrll
      _/BBB  _/rlrrr
     / \DD _/ \rlrrl
    /AA \_/ \_/rlrlr
   /AAAA  \C  \rlrll
  /AAAAAA  \_/rllr
_/AAAAAAAA   \rlll
 \DDDDDDDD   _/lrrrr
  \DDDDDD  _/ \lrrrl
   \DDDD  / \lrrl
    \DD _/B _/lrlrr
     \_/ \_/ \lrlrl
       \C  \lrll
        \_/llr
          \lll

There's more explanation here (although the tree is very slightly different).

Algorithm for maintaining balanced binary tree when adding a new node

Consider this approach:

At every node, maintain two values:

Max Left Depth: Maximum depth of a leaf in the left subtree
Max Right Depth: Maximum depth of a leaf in the right subtree

Choose the direction which has less max depth.

Recurse.

BTW, the example is misleading, you might start from a steady state when two sides are nearly balanced.

Is there a way to create a binary tree in Erlang using processes?

loop(N, Root, LeftNode, RightNode) -> 
 receive 
  create_nodes -> 
    MyPid = self(),
    NewLeftNode = spawn(?MODULE, loop, [N-1, MyPid, "empty-child-node", "empty-child-node"),
    NewRightNode = spawn(?MODULE, loop, [N-1, MyPid, "empty-child-node", "empty-child-node"]), 
    NewLeftNode ! create_nodes, 
    NewRightNode ! create_nodes, 
    loop(N, Root, NewLeftNode, NewRightNode); 

  _ -> ok 
end, 
loop(N, Root, LeftNode, RightNode).

Try this one out.

Binary tree maze generation in Elixir

On pattern you can use when mapping OO to sequential Elixir (functional language in general), you can create a data object (not an OO object) and pass it around as the first argument to your functions. This way, you are transforming that data on each call.

So, your api would be shaped like def link(maze, cell, bidirectional \\ true). Using a map to represent the maze with an {x,y} tuple as the key and a map as the value lets you access individual cells and update them.

Here is some untested code as an example.

def Maze do
  def new, do: %{cells: %{], links: %{}, start: {0,0}}}

  def link(maze, cell1, cell2, bidirectional \\ true) do
    maze
    |> put_in([:links, cell2], true)
    |> link_bidirectional(cell1, bidirectional)
  end

  defp link_bidirectional(maze, _, _, false), do: maze
  defp link_bidirectional(maze, cell1, cell2, _) do
    link(maze, cell2, cell1, false)
  end
end

EDIT: Here is a functional solution for linking

defmodule Maze do
  def new do 
    %{cells: %{{0, 0} => Cell.create(0,0)}, tree: {{0, 0}, nil, nil}}
  end

  def new_cell(maze, row, column) do
    # ignoring the tree for now
    put_in(maze, [:cells, {row, column}], Cell.create(row, column))
  end

  def link(maze, cell1, cell2, bidirectional \\ true)
  def link(maze, %{} = cell1, %{} = cell2, bidirectional) do
    maze
    |> update_in([:cells, cell1[:origin]], &(Cell.link(&1, cell2)))
    |> do_bidirectional(cell1, cell2, bidirectional, &link/4)
  end
  def link(maze, {_, _} = pt1, {_, _} = pt2, bidirectional) do
    link(maze, maze[:cells][pt1], maze[:cells][pt2], bidirectional)
  end

  def unlink(maze, %{} = cell1, %{} = cell2, bidirectional \\ true) do
    maze
    |> update_in([:cells, cell1[:origin]], &(Cell.unlink(&1, cell2)))
    |> do_bidirectional(cell1, cell2, bidirectional, &unlink/4)
  end

  defp do_bidirectional(maze, _, _, false, _), do: maze
  defp do_bidirectional(maze, cell1, cell2, _, fun) do
    fun.(maze, cell2, cell1, false)
  end
end

defmodule Cell do
  def create(row,column), do: %{origin: {row, column}, links: %{}}
  def link(self, cell) do
    update_in(self, [:links, cell[:origin]], fn _ -> true end)
  end
  def unlink(self, cell) do
    update_in(self, [:links], &Map.delete(&1, cell[:origin]))
  end
end

iex(26)> Maze.new() |>
...(26)> Maze.new_cell(0,1) |>
...(26)> Maze.new_cell(1,0) |>
...(26)> Maze.link({0,0}, {0,1}) |>
...(26)> Maze.link({0,0}, {1,0})
%{cells: %{{0,
     0} => %{links: %{{0, 1} => true, {1, 0} => true}, origin: {0, 0}},
    {0, 1} => %{links: %{{0, 0} => true}, origin: {0, 1}},
    {1, 0} => %{links: %{{0, 0} => true}, origin: {1, 0}}},
  tree: {{0, 0}, nil, nil}}
iex(27)>

Delete method in binary search tree: Original node not being deleted

Setting root = nil just nils the local reference. It doesn't nil the parent's right or left value, which is what you'd want to actually drop the node from the tree.

One way to work this might be to pass a block which gets invoked if the child doesn't have any child nodes. This captures the desired operation, and lets the recursed method call invoke it if it determines that the deletion should in fact occur.

  def delete(root=@root, value, &block)
    return root if root.data.nil?

    if root.data < value
      delete(root.right, value) { root.right = nil }
    elsif root.data > value
      delete(root.left, value) { root.left = nil }
    elsif root.right.nil? && root.left.nil?
      yield if block_given?
    end

    root
  end

(Additionally: there is a potential bug here. The first two conditions don't check if root.right or root.left are nil, and will attempt to recurse into them regardless. You may want to add additional guards for that possibility.)

Find deepest node(s) of a binary tree

Assumptions:

The Binary Tree is actually the root node
child_nodes returns the collection of child nodes as an array

class BinaryNode
  attr_reader :element

  def initialize(element,lchild,rchild)
    @element, @lchild, @rchild = element, lchild, rchild
  end

  def height
    if @lchild.nil? && @rchild.nil?
      return 0
    else
     [@lchild, @rchild].collect {|n| n.nil ? 0 : n.height + 1 }.max      
    end
  end

  def deepest_nodes
    return [self] if self.height == 1

    [@lchild, @rchild].select {|n| !n.nil? && (n.height == self.height - 1)}.collect {|n| n.deepest_nodes}.flatten
  end
end

Refactor:

class BinaryNode
  attr_reader :element

  def initialize(element,lchild,rchild)
    @element, @lchild, @rchild = element, lchild, rchild
  end

  def child_nodes
    [@lchild, @rchild].compact
  end

  def height
    if self.child_nodes.empty?
      return 0
    else
      self.child_nodes.collect {|n| n.height + 1 }.max      
    end
  end

  def deepest_nodes
    return [self] if self.depth == 1

    self.child_nodes.select {|n| n.height == self.height - 1}.collect {|n| n.deepest_nodes}.flatten
  end
end

Getting the elements:

BinaryNode.new(1,BinaryNode.new(2,leaf,leaf),BinaryNode.new(3,leaf,leaf)).deepest_nodes.collect {|n| n.element }

Algorithm to Render a Horizontal Binary-Ish Tree in Text/Ascii Form