Code to test if a tree is balanced

This is a discussion on Code to test if a tree is balanced within the C Programming forums, part of the General Programming Boards category; Hi, I am trying to write code to test if a tree is balanced. The function will take a pointer ...

  1. #1
    Registered User
    Join Date
    Mar 2003
    Posts
    6

    Code to test if a tree is balanced

    Hi,
    I am trying to write code to test if a tree is balanced.
    The function will take a pointer to the root node of the tree and will have to figure out if the tree is balanced.
    The tree is a normal binary tree.
    Any ideas/code?

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    A binary tree if perfectly balanced if the height of the left child is the same as the height of the right child. Normally, a balanced tree algorithm will relax this condition so that the height of the left and right child can differ by at most 1.
    Whatever "balanced" means to you, all you need is a recursive function to calculate the height of a given node. Then you can recursively check that every node in the tree is balanced. This will be very inefficient though.

    Look up an implementation of an AVL tree if your not sure how to implement the recursion.

    gg

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problem in creating a tree
    By Lorin_sz in forum C++ Programming
    Replies: 2
    Last Post: 09-26-2005, 01:28 PM
  2. problem in creating a tree
    By Lorin_sz in forum C Programming
    Replies: 1
    Last Post: 09-26-2005, 01:24 PM
  3. Obfuscated Code Contest
    By Stack Overflow in forum Contests Board
    Replies: 51
    Last Post: 01-21-2005, 03:17 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21