2/05/2012

Drawing Recursion Tree through LaTex

Finally, I learned how to draw recursion tree using latex. There is a package called TikZ which can construct beautiful and clean pictures that can directly be embedded into latex.
http://www.texample.net/tikz/
Below is a tree I drew for algorithm homework:
\begin{tikzpicture}[level/.style={sibling distance=40mm/#1}]
\node (z){$n$}
  child {node (a) {$\frac{n}{3}$}
    child {node  (b) {$\frac{n}{9}$}
      child {node (b1) {$\vdots$}
      child {node (b11) {$D$}}
      }
      child {node (b2) {$\vdots$}
      child {node (b12) {$D$}}
      }
    }
    child {node (g) {$\frac{n}{9}$}
      child {node (g1) {$\vdots$}
      child {node (g11) {$D$}}
      }
      child {node (g2) {$\vdots$}
      child {node (g12) {$D$}}
      }
    }
  }
    child {node (d) {$\frac{n}{3}$}
      child {node  (e) {$\frac{n}{9}$}
        child {node (e1) {$\vdots$}
        child {node (e11) {$D$}}
        }
        child {node (e2) {$\vdots$}
        child {node (e12) {$D$}}
        }
      }
      child {node (f) {$\frac{n}{9}$}
        child {node (f1) {$\vdots$}
        child {node (f11) {$D$}}
        }
        child {node (f2) {$\vdots$}
        child {node (f12) {$D$}}
        }
      }
    }
  child {node  (j) {$\frac{n}{3}$}
    child {node (k) {$\frac{n}{9}$}
      child {node {$\vdots$}
      child {node (k11) {$D$}}
      }
      child {node {$\vdots$}
      child {node (k12) {$D$}}
      }
    }
    child {node (l) {$\frac{n}{9}$}
    child {node {$\vdots$}
    child {node (l11) {$D$}}
    }
    child {node (c){$\vdots$}
    child {node (l12) {$D$}
            child [grow=right] {node (r) {$n$} edge from parent[draw=none]
              child [grow=up] {node (s) {$\vdots$} edge from parent[draw=none]
                child [grow=up] {node (t) {$n$} edge from parent[draw=none]
                  child [grow=up] {node (u) {$n$} edge from parent[draw=none]
                  child [grow=up] {node (u) {$n$} edge from parent[draw=none]}
                  }
                }
              }
            }
            }
    }
  }
};
\path (b) -- (g) node [midway] {$\cdots$};
\path (e) -- (f) node [midway] {$\cdots$};
\path (k) -- (l) node [midway] {$\cdots$};
\path (b11) -- (b12) node [midway] {$\cdots$};
\path (g11) -- (g12) node [midway] {$\cdots$};
\path (e11) -- (e12) node [midway] {$\cdots$};
\path (f11) -- (f12) node [midway] {$\cdots$};
\path (k11) -- (k12) node [midway] {$\cdots$};
\path (l11) -- (l12) node [midway] {$\cdots$};
\end{tikzpicture}