This is part of my own implementation of BST. The ugly part of this problem is that you have to know the space that your children occupies before you can print out yourself. Because you can have very big numbers like 217348746327642386478832541267836128736..., but also small numbers like 10, so if you have a parent-children relationship between these two, then it can potentially overlap with your other child. Therefore, we need to first go through the children, make sure we get how much space they are having, then we use that information to construct ourself.
def __str__[self]:
h = self.getHeight[]
rowsStrs = ["" for i in range[2 * h - 1]]
# return of helper is [leftLen, curLen, rightLen] where
# leftLen = children length of left side
# curLen = length of keyStr + length of "_" from both left side and right side
# rightLen = children length of right side.
# But the point of helper is to construct rowsStrs so we get the representation
# of this BST.
def helper[node, curRow, curCol]:
if[not node]: return [0, 0, 0]
keyStr = str[node.key]
keyStrLen = len[keyStr]
l = helper[node.l, curRow + 2, curCol]
rowsStrs[curRow] += [curCol -len[rowsStrs[curRow]] + l[0] + l[1] + 1] * " " + keyStr
if[keyStrLen < l[2] and [node.r or [node.p and node.p.l == node]]]:
rowsStrs[curRow] += [l[2] - keyStrLen] * "_"
if[l[1]]:
rowsStrs[curRow + 1] += [len[rowsStrs[curRow + 2]] - len[rowsStrs[curRow + 1]]] * " " + "/"
r = helper[node.r, curRow + 2, len[rowsStrs[curRow]] + 1]
rowsStrs[curRow] += r[0] * "_"
if[r[1]]:
rowsStrs[curRow + 1] += [len[rowsStrs[curRow]] - len[rowsStrs[curRow + 1]]] * " " + "\\"
return [l[0] + l[1] + 1, max[l[2] - keyStrLen, 0] + keyStrLen + r[0], r[1] + r[2] + 1]
helper[self.head, 0, 0]
res = "\n".join[rowsStrs]
#print["\n\n\nStart of BST:****************************************"]
#print[res]
#print["End of BST:****************************************"]
#print["BST height: ", h, ", BST size: ", self.size]
return res
Here's some examples of running this:
[26883404633, 10850198033, 89739221773, 65799970852, 6118714998, 31883432186, 84275473611, 25958013736, 92141734773, 91725885198, 131191476, 81453208197, 41559969292, 90704113213, 6886252839]
26883404633___________________________________________
/ \
10850198033__ 89739221773___________________________
/ \ / \
6118714998_ 25958013736 65799970852_______________ 92141734773
/ \ / \ /
131191476 6886252839 31883432186_ 84275473611 91725885198
\ / /
41559969292 81453208197 90704113213
Another example:
['rtqejfxpwmggfro', 'viwmdmpedzwvvxalr', 'mvvjmkdcdpcfb', 'ykqehfqbpcjfd', 'iuuujkmdcle', 'nzjbyuvlodahlpozxsc', 'wdjtqoygcgbt', 'aejduciizj', 'gzcllygjekujzcovv', 'naeivrsrfhzzfuirq', 'lwhcjbmcfmrsnwflezxx', 'gjdxphkpfmr', 'nartcxpqqongr', 'pzstcbohbrb', 'ykcvidwmouiuz']
rtqejfxpwmggfro____________________
/ \
mvvjmkdcdpcfb_____________________________ viwmdmpedzwvvxalr_______________
/ \ \
iuuujkmdcle_________ nzjbyuvlodahlpozxsc_ ykqehfqbpcjfd
/ \ / \ /
aejduciizj_____________ lwhcjbmcfmrsnwflezxx naeivrsrfhzzfuirq_ pzstcbohbrb wdjtqoygcgbt_
\ \ \
gzcllygjekujzcovv nartcxpqqongr ykcvidwmouiuz
/
gjdxphkpfmr
How do I display a binary search tree in Python?
To insert into a tree we use the same node class created above and add a insert class to it. The insert class compares the value of the node to the parent node and decides to add it as a left node or a right node. Finally the PrintTree class is used to print the tree.
How do I print a binary search tree?
You start traversing from the root, then go to the left node, then you again go to the left node until you reach a leaf node. At that point in time, you print the value of the node or mark it as visited and move to the right subtree. Continue the same algorithm until all nodes of the binary tree are visited.
How do you print tree structure in Python?
To print all nodes of a tree using depth-first search, only few lines are required:.
def printTree[root, level=0]:.
print[" " * level, root.x].
for child in root.children:.
printTree[child, level + 1].
#tree = Node[..., children=[Node[...., ...], Node[...,....]] ... .
printTree[tree].
How do I print BST in ascending order?
Given an array that stores a complete Binary Search Tree, write a function that efficiently prints the given array in ascending order. Solution: Inorder traversal of BST prints it in ascending order. The only trick is to modify recursion termination condition in standard Inorder Tree Traversal.