General Information

The following two figures refer to the radix-2 FFT algorithm’s recursive tree. The first one depicts the recursive calls done in each stage, whereas the second pictorially outlines the intuition behind the bit-reversal permutation.

Recursive Tree

\documentclass{standalone}

\usepackage[edges]{forest}

\begin{document}
	\begin{forest}
		for tree={
			draw,
			fill=gray!30,
			s sep+=3ex,
			l sep+=4ex,
			math content,
			edge={semithick},
			where n children={0}{}{label={}}}
		[{
			a_{0}~~
			a_{1}~~
			a_{2}~~
			a_{3}~~
			a_{4}~~
			a_{5}~~
			a_{6}~~
			a_{7}
		  }
		 [{
		 	a_{0}~~
		 	a_{2}~~
		 	a_{4}~~
		 	a_{6}
		  }
		  [{
		  	a_{0}~~
		  	a_{4}
		   }
		   [a_{0}]
		   [a_{4}]
		  ]
		  [{
		  	a_{2}~~
		  	a_{6}
		   }
		   [a_{2}]
		   [a_{6}]
		  ]
		 ]
		 [{
		 	a_{1}~~
		 	a_{3}~~
		 	a_{5}~~
		 	a_{7}
		  }
		  [{
		  	a_{1}~~
		  	a_{5}
		  }
		   [a_{1}]
		   [a_{5}]
		  ]
		  [{
		  	a_{3}~~
		  	a_{7}
		   }
		   [a_{3}]
		   [a_{7}]
		  ]
		 ]
		];
	\end{forest}
\end{document}

Recursive Tree – Binary

\documentclass{standalone}

\usepackage[edges]{forest}
\usepackage{xcolor}

\definecolor{mycolor0}{RGB}{44, 117, 226}
\definecolor{mycolor1}{RGB}{255, 103, 15}

\begin{document}
	\begin{forest}
		for tree={
			draw,
			fill=gray!30,
			s sep+=1ex,
			l sep+=4ex,
			math content,
			edge={semithick},
			where n children={0}{}{label={}}}
		[{
			a_{00{\color{mycolor0}0}}~~
			a_{00{\color{mycolor1}1}}~~
			a_{01{\color{mycolor0}0}}~~
			a_{01{\color{mycolor1}1}}~~
			a_{10{\color{mycolor0}0}}~~
			a_{10{\color{mycolor1}1}}~~
			a_{11{\color{mycolor0}0}}~~
			a_{11{\color{mycolor1}1}}
		  }
		 [{
		 	a_{0{\color{mycolor0}0}0}~~
		 	a_{0{\color{mycolor1}1}0}~~
		 	a_{1{\color{mycolor0}0}0}~~
		 	a_{1{\color{mycolor1}1}0}
		  }, for tree={edge=mycolor0}
		  [{
		  	a_{{\color{mycolor0}0}00}~~
		  	a_{{\color{mycolor1}1}00}
		   }
		   [a_{000}, for tree={edge=mycolor0}]
		   [a_{100}, for tree={edge=mycolor1}]
		  ]
		  [{
		  	a_{{\color{mycolor0}0}10}~~
		  	a_{{\color{mycolor1}1}10}
		   }, for tree={edge=mycolor1}
		   [a_{010}, for tree={edge=mycolor0}]
		   [a_{110}, for tree={edge=mycolor1}]
		  ]
		 ]
		 [{
		 	a_{0{\color{mycolor0}0}1}~~
		 	a_{0{\color{mycolor1}1}1}~~
		 	a_{1{\color{mycolor0}0}1}~~
		 	a_{1{\color{mycolor1}1}1}
		  }, for tree={edge=mycolor1}
		  [{
		  	a_{{\color{mycolor0}0}01}~~
		  	a_{{\color{mycolor1}1}01}
		  }, for tree={edge=mycolor0}
		   [a_{001}, for tree={edge=mycolor0}]
		   [a_{101}, for tree={edge=mycolor1}]
		  ]
		  [{
		  	a_{{\color{mycolor0}0}11}~~
		  	a_{{\color{mycolor1}1}11}
		   }, for tree={edge=mycolor1}
		   [a_{011}, for tree={edge=mycolor0}]
		   [a_{111}, for tree={edge=mycolor1}]
		  ]
		 ]
		];
	\end{forest}
\end{document}