# How can I create a Binary Search Tree with Linked Lists on every node?

I'm trying to create a Binary Search Tree with Linked Lists on every node, something like the picture but the blue arrows are not desired. I'm currently using tikz-qtree to create my trees.

Current tree:

\tikzset{every tree node/.style={minimum width=2em,draw,circle},
blank/.style={draw=none},
edge from parent/.style=
{draw, edge from parent path={(\tikzparentnode) -- (\tikzchildnode)}},
level distance=1.5cm}
\begin{tikzpicture}
\Tree
[.2,1
[.1,2
[.0,2
\edge[blank]; \node[blank]{};
[.0,3
\edge[blank]; \node[blank]{};
[.0,4 ]
]
]
[.1,4 ]
]
[.2,2 ]
]
\end{tikzpicture}


• I can draw simple tree, but I don't know how I can add a linked list to a node. I posted the current tree code. BST means binary search tree. – Nicolò Ciraci Sep 12 '16 at 14:34
• the shown tree does not look like a BST (binary Search Tree) to me. more like a left shifted disfigured tree. maybe if you could clearify you intentions, the community could provide better help. – naphaneal Sep 12 '16 at 14:44
• I don't understand how I can be more specific, I would like that my tree have a linked list starting from every node, just like the picture below. What is the problem with the tree? It is a not balanced binary search tree using two key for comparison. – Nicolò Ciraci Sep 12 '16 at 14:47
• You can just use TikZ to add the list nodes since you're using tikz-qtree. I'd use Forest, but that's because I like it and could probably automate it so Forest placed all or most of the list nodes for me. tikz-qtree doesn't have the same power, but you can use the full power of TikZ to do the job. – cfr Sep 12 '16 at 15:22
• In any case, please provide complete code. How is blank defined? Presumably you are loading tikz-qtree? Anything else needed for the example? (Or does tikz-qtree defineblank?) – cfr Sep 12 '16 at 15:35

Here's how I would do it. This solution defines a forest style binary search tree.

For each node within the tree, it is possible to typeset a second node to the right or left, to contain the list. If this is desired, the content of the node should be specified in the form

<content of main node>:<content of secondary node>


Because the contents of all nodes include commas in this case, the form

{<content of main node>}:{<content of secondary node>}


is needed. Translating your code and adding some secondary nodes, for example,

\begin{forest}
binary search tree,
[{2,1}:{1,1}
[{1,2}:{0,1}
[{0,2}:{2,2}
[,phantom]
[{0,3}:{1,4}
[,phantom]
[{0,4}:{-3,0}]
]
]
[{1,4}:{0,-1}]
]
[{2,2}:{-1,1}]
]
\end{forest}


produces

You said that the blue/green arrows were not required, so I've left the tree plain. However, these could easily be added using the tikz or tikz+ keys, if desired.

Complete code:

\documentclass[border=10pt,multi,tikz]{standalone}
\usepackage{forest}
\forestset{%
list me/.style={draw, no edge},
list node/.style={%
if level=0{%
label={[draw, anchor=east, label distance=5pt]left:{#1}},
}{%
if n=1{%
insert before={[{#1}, list me]},
}{%
if={strequal((content("!u1")),"")}{%
for nodewalk={fake=u,n=1}{%
insert before={[{#1},phantom]},
},
}{},
insert after={[{#1}, list me]},
},
},
},
binary search tree/.style={%
for tree={%
circle,
draw,
},
delay={%
for tree={%
split option={content}{:}{content,list node},
},
},
before typesetting nodes={%
where content={}{%
if nodewalk valid={s}{%
content/.wrap pgfmath arg={##1}{content("!s")},
}{},
}{},
},
},
}
\begin{document}
\begin{forest}
binary search tree,
[{2,1}:{1,1}
[{1,2}:{0,1}
[{0,2}:{2,2}
[,phantom]
[{0,3}:{1,4}
[,phantom]
[{0,4}:{-3,0}]
]
]
[{1,4}:{0,-1}]
]
[{2,2}:{-1,1}]
]
\end{forest}
\end{document}