2.3c.py

import copy

main = {
		3: {
			2: None,
			10:
				{
					1: None,
					7:
						{
							12:
								{
									13: None,
									"h": 0,
									"root": -1
								},
							"h": 0,
							"root": -1
						},
					"h": 0,
					"root": -1
				},
			"h": 0,
			"root": -1
		},
		"h": 0,
		"root": 3
}

def fix_h_0(d):
	for k, v in d.iteritems():
		for k, v in d.iteritems():
			if isinstance(v, dict):
				fix_h_0(v)

			d["h"] = 0

def fix_h(d):
	for k, v in d.iteritems():
		if isinstance(v, dict):
			fix_h(v)

			if v["h"]+1 > d["h"]:
				d["h"] = v["h"]+1

def _find(d, x, root=None):
	global path

	if d["root"] >= 0:
		root = d["root"]

	for k, v in d.iteritems():
		if k == x:
			path.append(k)
			return root
		elif isinstance(v, dict):
			path.append(k)
			return find(v, x, root)

def find(d, x, root=None):
	global path

	root = _find(d, x, root)

	if root >= 0:
		for k, v in main[root].iteritems():
			if isinstance(k, int):
				if k in path:
					path.remove(k)

		if root in path:
			path.remove(root)
		path.reverse()

	if root >= 0:
		for p in path:
			compress(main, p, root)

	fix_h_0(main)
	fix_h(main)

	return root

def compress(d, x, root):
	for k, v in d.iteritems():
		if k == x:
			main[root][k] = copy.deepcopy(v)
			del d[k]

			return
		elif isinstance(v, dict):
			return compress(v, x, root)

path = []

fix_h_0(main)
fix_h(main)

print "h: ", main["h"]

root = find(main, 12)

print "find(12): ", root

print "h: ", main["h"]

# print main