# Find all the paths which sum up to the target value in a tree

From: http://stackoverflow.com/questions/4591763/find-paths-in-a-binary-search-tree-summing-to-a-target-value

[Problem]

Given a binary search tree and a target value, find all the paths (if there exists more than one) which sum up to the target value. It can be any path in the tree. It doesn't have to be from the root.

Please explain logic.

Moreover,in the following binary search tree:

    2  / \  1   3  

when the sum should be 6, then the path 1 -> 2 -> 3 should also be printed

[Solution]

Traverse through the tree from the root and do a post-order gathering of all path sums. Use a hashtable to store the possible paths rooted at a node and going down-only. We can construct all paths going through a node from itself and its childrens' paths.

Here is psuedo-code that implements the above, but stores only the sums and not the actual paths. For the paths themselves, you need to store the end node in the hashtable (we know where it starts, and there's only one path between two nodes in a tree).

  function findsum(tree, target)   # Traverse the children   if tree->left     findsum(tree.left, target)   if tree->right     findsum(tree.right, target)    # Single node forms a valid path   tree.sums = {tree.value}    # Add this node to sums of children   if tree.left     for left_sum in tree.left.sums       tree.sums.add(left_sum + tree.value)   if tree.right     for right_sum in tree.right.sums       tree.sums.add(right_sum + tree.value)    # Have we formed the sum?   if target in tree.sums     we have a path    # Can we form the sum going through this node and both children?   if tree.left and tree.right     for left_sum in tree.left.sums       if target - left_sum in tree.right.sums         we have a path    # We no longer need children sums, free their memory   if tree.left     delete tree.left.sums   if tree.right     delete tree.right.sums 

This doesn't use the fact that the tree is a search tree, so it can be applied to any binary tree.

For large trees, the size of the hashtable will grow out of hand. If there are only positive values, it could be more efficient to use an array indexed by the sum.

# Traverse the tree in O(n) time and O(1) space

http://tomazos.com/tomazos-binary-tree-traverse/

By Andrew Tomazos andrew@tomazos.com http://www.tomazos.com 2008-11-10

We describe an algorithm that traverses a binary tree in O(n) time and O(1) space. Each node is visited exactly three times, once preorder, once inorder and once postorder.

Description

Imagine each node in the binary tree is a castle. Imagine that, relative to its parent, each left and right child castle is built southwestward and southeastward respectively. Now imagine each edge is a high wall connecting two castles.

We start on the ground outside of the root castle directly to its west. We start to walk south initially, and turn as necessary to always keeping the unified boundary formed by the castles and walls on our left flank. Once we reach the east side of the root castle, we will have passed by every castles westside, southside and eastside exactly once.

Each time we pass the Westside of a castle, we are visiting it preorder.

Each time we pass the Southside of a castle, we are visiting it inorder.

Each time we pass the Eastside of a castle, we are visiting it postorder.

It is possible to simulate this journey only keeping local information:

1. The current castle
2. Which of the three important sides (WEST, SOUTH, EAST) we are on of the current castle.
3. The current castles left and right child, if any.
4. The current castles parent, if any
5. If the current castle has a parent, whether the current castle is the left or right child of its parent.

# How to calculate the height in a binary search tree. 

This is a very good post explains the height and corresponding balance for tree.

http://stackoverflow.com/questions/575772/the-best-way-to-calculate-the-height-in-a-binary-search-tree-balancing-an-avl-t

Also see: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx

(a) two different definitions of the height of the tree:

one focuses on nodes: 

  height(node):     if node == null:         return 0    else:         max(height(node.L), height(node.R)) + 1

one focuses on edges:

  height(node):     if node == null:         return -1    else:         max(height(node.L), height(node.R)) + 1

(b) Note that the balance factor is: left - right

BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

--

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥